#pragma once

#include "UnrealProject.h"
#include <unordered_set>
using namespace std;


class ACharacterBase;
namespace MiniMap
{
	struct Rect
	{
		Rect() = default;
		Rect(float x, float y, float width, float height) : x(x), y(y), width(width), height(height) {}
		Rect(const FVector2D& position, const FVector2D& size) : x(position.X), y(position.Y), width(size.X), height(size.Y) {}
		float x;
		float y;
		float width;
		float height;

		inline FVector2D position() const
		{
			return FVector2D(x, y);
		}
		inline FVector2D size() const
		{
			return FVector2D(width, height);
		}
		inline bool contains(const FVector2D& pos) const
		{
			return pos.X >= x && pos.X <= (x + width) && pos.Y >= y && pos.Y <= (y + height);
		}
	};


	inline Rect GetSubArea(const Rect& area, size_t idx)
	{
		const FVector2D half_size = area.size() / 2;
		const FVector2D position = area.position();
		switch (idx)
		{
		case 0: return Rect(position, half_size);
		case 1: return Rect(position + FVector2D(half_size.X, 0), half_size);
		case 2: return Rect(position + half_size, half_size);
		case 3: return Rect(position + FVector2D(0, half_size.Y), half_size);
		}
		return area;
	}
	inline bool RectCircleOverlapSquared(const Rect& area, const FVector2D& position, float radius_sqr)
	{
		const FVector2D pos = area.position();
		const float left = area.x;
		const float bottom = area.y;
		const float right = area.x + area.width;
		const float top = area.y + area.height;

		const float x = position.X > right ? right : position.X < left ? left : position.X;
		const float y = position.Y > top ? top : position.Y < bottom ? bottom : position.Y;

		return FVector2D::DistSquared(position, FVector2D(x, y)) <= radius_sqr;
	}

	class NonCopyable
	{
	public:
		NonCopyable() = default;
		NonCopyable(const NonCopyable& other) = delete;
		NonCopyable& operator=(const NonCopyable& other) = delete;
	};

	class MinimapHandle;
	class NodeBase : private NonCopyable
	{
	protected:
		NodeBase(const Rect& area, NodeBase* parent) : area(area), parent(parent) {}

	public:
		virtual void AddObject(MinimapHandle& obj) = 0;
		virtual void RemoveObject(MinimapHandle& obj) = 0;
		virtual void ClearRecursive()
		{
			objects.clear();
		}
		virtual void ResizeRecursive(const Rect& area)
		{
			this->area = area;
		}

		virtual void CircleOverlap(const FVector2D& position, float radius_sqr, TArray<MinimapHandle*>& out_objects);

		unordered_set<MinimapHandle*> objects;
		Rect area;
		NodeBase* parent;
	};

	class MinimapHandle : private NonCopyable
	{
	public:
		MinimapHandle() : character(nullptr), node(nullptr), root(nullptr) {}
		MinimapHandle(const FVector2D& position) : character(nullptr), position(position), node(nullptr), root(nullptr) {}
		~MinimapHandle()
		{
			
		}

		FVector2D position;
		class ::ACharacterBase* character;
		NodeBase* node;
		NodeBase* root;
	};

	template<size_t level> class TreeNode : public NodeBase
	{
	public:
		TreeNode(const Rect& area, NodeBase* parent) : NodeBase(area, parent), child0(GetSubArea(area, 0), this), child1(GetSubArea(area, 1), this), child2(GetSubArea(area, 2), this), child3(GetSubArea(area, 3), this) {}

		typedef TreeNode<level - 1> child_type;
		child_type child0;
		child_type child1;
		child_type child2;
		child_type child3;
		unordered_set<MinimapHandle*> child_objects;

		virtual void AddObject(MinimapHandle& obj) override
		{
			child_type* children = &child0;
			for (size_t i = 0; i < 4; i++)
			{
				if (children[i].area.contains(obj.position))
				{
					// Register to child
					child_objects.emplace(&obj);
					children[i].AddObject(obj);
					return;
				}
			}

			// Register to this node
			objects.emplace(&obj);
			obj.node = this;
		}
		virtual void RemoveObject(MinimapHandle& obj) override
		{
			// Check if present in children
			auto find_child = child_objects.find(&obj);
			if (find_child != child_objects.end())
			{
				child_type* children = &child0;
				for (size_t i = 0; i < 4; i++)
					children[i].RemoveObject(obj);

				child_objects.erase(find_child);
			}
			else
			{
				// Remove from node
				auto find = objects.find(&obj);
				if (find != objects.end())
					objects.erase(find);
			}
		}
		virtual void ClearRecursive() override
		{
			child_type* children = &child0;
			for (size_t i = 0; i < 4; i++)
				children[i].ClearRecursive();

			NodeBase::ClearRecursive();
			child_objects.clear();
		}
		virtual void ResizeRecursive(const Rect& area) override
		{
			child_type* children = &child0;
			for (size_t i = 0; i < 4; i++)
				children[i].ResizeRecursive(GetSubArea(area, i));

			NodeBase::ResizeRecursive(area);
		}

		virtual void CircleOverlap(const FVector2D& position, float radius_sqr, TArray<MinimapHandle*>& out_objects) override
		{
			if (!child_objects.empty())
			{
				child_type* children = &child0;
				for (size_t i = 0; i < 4; i++)
				{
					child_type& child = children[i];
					if (RectCircleOverlapSquared(child.area, position, radius_sqr))
						child.CircleOverlap(position, radius_sqr, out_objects);
				}
			}

			NodeBase::CircleOverlap(position, radius_sqr, out_objects);
		}
	};
	template<size_t level> class RootNode : public TreeNode<level>
	{
	public:
		RootNode(const Rect& area, NodeBase* parent) : TreeNode<level>(area, parent)
		{

		}

		virtual void AddObject(MinimapHandle& obj) override
		{
			TreeNode<level>::AddObject(obj);
			all_objects.emplace(&obj);
		}
		virtual void RemoveObject(MinimapHandle& obj) override
		{
			TreeNode<level>::RemoveObject(obj);
			auto find = all_objects.find(&obj);
			if (find != all_objects.end())
				all_objects.erase(find);
		}
		virtual void ClearRecursive() override
		{
			for (auto iter = all_objects.begin(); iter != all_objects.end(); iter++)
			{
				(*iter)->node = nullptr;
				(*iter)->root = nullptr;
			}
			all_objects.clear();

			TreeNode<level>::ClearRecursive();
		}

		void Reparent(MinimapHandle& obj)
		{
			TreeNode<level>::RemoveObject(obj);
			TreeNode<level>::AddObject(obj);
		}

		unordered_set<MinimapHandle*> all_objects;
	};
	template<> class TreeNode<0> : public NodeBase
	{
	public:
		TreeNode(const Rect& area, NodeBase* parent) : NodeBase(area, parent)
		{

		}

		void AddObject(MinimapHandle& obj) override
		{
			objects.emplace(&obj);
			obj.node = this;
		}
		void RemoveObject(MinimapHandle& obj) override
		{
			auto find = objects.find(&obj);
			if (find != objects.end())
				objects.erase(find);
		}
	};

	template<size_t depth> class QuadTree : private NonCopyable
	{
	public:
		QuadTree() : m_root_node(Rect(0, 0, 1, 1), nullptr) {}
		QuadTree(const Rect& area) : m_root_node(area, nullptr) {}
		~QuadTree()
		{
			m_root_node.ClearRecursive();
		}

		void AddObject(MinimapHandle& obj)
		{
			if (obj.root == &m_root_node)
				return;
			if (obj.root != nullptr)
				obj.root->RemoveObject(obj);

			// Add object to root
			m_root_node.AddObject(obj);
			obj.root = &m_root_node;
		}
		void RemoveObject(MinimapHandle& obj)
		{
			if (obj.root == nullptr)
				return;
			if (obj.root != &m_root_node)
				return;

			// Remove from root
			m_root_node.RemoveObject(obj);
			obj.node = nullptr;
			obj.root = nullptr;
		}

		void Update()
		{
			// Update positioning
			for (auto iter = m_root_node.all_objects.begin(); iter != m_root_node.all_objects.end(); iter++)
			{
				MinimapHandle& obj = **iter;

				if (!obj.node->area.contains(obj.position) && obj.node->parent)
					m_root_node.Reparent(obj);
			}
		}
		void Clear()
		{
			m_root_node->ClearRecursive();
		}
		void Resize(const Rect& area)
		{
			m_root_node.ResizeRecursive(area);
		}

		int32 Num() const
		{
			return int32(m_root_node.all_objects.size());
		}

		bool CircleOverlap(const FVector2D& position, float radius, TArray<MinimapHandle*>& out_objects)
		{
			out_objects.SetNum(0);
			m_root_node.CircleOverlap(position, radius * radius, out_objects);
			return out_objects.Num() > 0;
		}

		RootNode<depth> m_root_node;
	};
}