#ifndef ROAD_GRID_H
#define ROAD_GRID_H
#include <cassert>
#include <unordered_map>
#include <core/object.h>
#include <core/reference.h>
#include <scene/resources/curve.h>
#include <core/math/random_number_generator.h>
#include <core/math/a_star.h>
#include <modules/voxel/util/noise/fast_noise_lite.h>

class CanvasItem;

/* TODO:
 * a
 * - Implement diagram edges with site reference.
 * - Implement draw edges according to current position,
 *   indicating which are drawn.
 * - Implement removal of draw edges by distance
 *
 * - Rewrite debug draw using distance logic.
 * - Implement 3D position for road vertices based on heightmap object;
 * - Implement SDF influence calculation based on distance to road
 * - Implement SDF calculation for roads (height cutoff by segment)
 * b
 * - Implement nodes (intersections) for drawing road intersections
 * - Implement draw edge splitting and position improvement.
 * - Find "wall" edges?
 * c
 * - Implement lot system based on sites
 * - Split lots to place buildings and other environment
 *   objects
 * d
 * - Implement 3D positions and geometry generation
 */

struct cluster {
	Vector2i c;
	float r;
};
struct graphedge {
	int a, b;
	int edge;
};
struct map_site {
	enum {
		SITE_UNASSIGNED = 0,
		SITE_FOREST,
		SITE_TOWN,
		SITE_FARM,
		SITE_EMPTY,
		SITE_MAX
	};
	int index, diagram_index;
	Vector2 pos;
	Vector<struct graphedge> graphedges;
	Vector<Vector2> vertices;
	Vector<Vector2> polygon;
	Vector<int> vertices_ind;
	Vector<int> polygon_ind;
	int site_type;
	int cluster;
	Vector<struct half_edge> hedges;
	Vector2 building_positions;
	Rect2i rect;
	float avg_height;
};
struct half_edge {
	int a, b;
	int site;
	float depth;
	float length;
};
struct vshape {
	AABB area;
	int instance;
	int e1, e2;
	int site;
	Vector3 p1, p2, p3;
	float depth1, depth2;

	/* filled later */
	float total_width1,
	      total_width2;
	PoolVector<String> parts_list1,
		parts_list2;
	Ref<Curve3D> curve3;
	Ref<Curve3D> curve3a;
};
class RoadDiagram {
protected:
	List<struct cluster> clusters;
	Vector<struct map_site> map_sites;
	Vector<Vector2> diagram_vertices;
	Vector<struct half_edge *> map_hedges;
	HashMap<int, int> class_sizes;
	void classify_sites()
	{
		int i, j;
		for (j = 0; j < map_sites.size(); j++) {
			Rect2 r;
			for (i = 0; i < map_sites[j].polygon.size(); i++) {
				if (i == 0) {
					r.position = map_sites[j].polygon[0];
					r.size = Vector2();
				} else {
					r.expand_to(map_sites[j].polygon[i]);
				}
			}
			int cl_area = (int)(r.get_area() + 1.0f);
			for (i = 0; i < map_site::SITE_MAX; i++) {
				if (class_sizes.has(i)) {
					if (cl_area >= class_sizes[i]) {
						map_sites.write[j].site_type = i;
						break;
					}
				}
			}
			/* for now the starting town is at 0 */
			printf("area: %d class: %d\n", cl_area, map_sites[j].site_type);
		}
		map_sites.write[0].site_type = map_site::SITE_TOWN;
	}
	void index_site(struct map_site *site);
	Dictionary build_diagram(Ref<RandomNumberGenerator> rnd,
			int npatches, int center_count, int center_step,
			int spread, int dim);
	void process_diagram(const Dictionary &diagram);
public:
	RoadDiagram();
	void set_class_size(int cl, int sz)
	{
		class_sizes[cl] = sz;
	}
	const List<struct cluster> &get_clusters() const;
	const Vector<struct map_site> &get_map_sites() const;
	const Vector<Vector2> &get_diagram_vertices() const;
	const Vector<struct half_edge *> &get_map_hedges() const;
	void build(Ref<RandomNumberGenerator> rnd,
			int npatches, int center_count, int center_step,
			int spread, int dim);
};

class RoadGrid: public Reference {
	GDCLASS(RoadGrid, Object)
protected:
	Ref<RandomNumberGenerator> rnd;
	Ref<AStar> astar;
	int keep_seed;
	List<struct cluster> clusters;
	Rect2 bounds;
	static void _bind_methods();
	Vector<Vector2> diagram_vertices;
	Vector<struct map_site> map_sites;
	Vector<struct half_edge *> map_hedges;
	PoolVector<Vector3> vertices;
	PoolVector<struct vshape> vshapes;
	bool segment_intersects_rect(const Vector2 &a, const Vector2 &b, const Rect2 &rect);
	inline bool segment_in_grid_rect(const Vector2 &a, const Vector2 &b, int x, int y)
	{
		Rect2 r((float)(x * grid_width), (float)(y * grid_height), grid_width, grid_height);
		return segment_intersects_rect(a, b, r);
	}
	inline Rect2 segment_to_rect(const Vector2 &a, const Vector2 &b) const
	{
		Rect2 r(a, Vector2());
		r.expand_to(b);
		return r;
	}
	inline Rect2i rect_to_grid(const Rect2 &r) const
	{
		Rect2i ret;
		ret.position.x = get_grid_x(r.position.x);
		ret.position.y = get_grid_y(r.position.y);
		ret.size.x = get_grid_x(r.size.x) + 1;
		ret.size.y = get_grid_y(r.size.y) + 1;
		return ret;
	}
	inline Rect2 get_grid_rect(int x, int y) const
	{
		Rect2 rect;
		rect.position.x = (float)x * grid_width;
		rect.position.y = (float)y * grid_height;
		rect.size.x = grid_width;
		rect.size.x = grid_height;
		return rect;
	}
	class hg {
		typedef Vector<struct half_edge *> tvalue;
		std::unordered_map<int, std::unordered_map<int, Vector<struct half_edge *> > > hedge_grid;
	public:
		inline const tvalue get(int x, int y) const
		{
			return hedge_grid.at(x).at(y);
		}
		inline bool has(int x, int y) const
		{
			if (hedge_grid.find(x) != hedge_grid.end() &&
					hedge_grid.at(x).find(y) != hedge_grid.at(x).end())
				return true;
			return false;
		}
		inline void set(int x, int y, struct half_edge *hedge)
		{
			Vector<struct half_edge *> items;
			if (has(x, y))
				items = get(x, y);
			items.resize(items.size() + 1);
			items.write[items.size() - 1] = hedge;
			hedge_grid[x][y] = items;
		}
		inline void insert_hedge_to_grid_cell(int x, int y, struct half_edge *hedge)
		{
			set(x, y, hedge);
		}
	};
	class hg hedge_grid;
	inline void add_hedge_to_grid(struct half_edge *hedge)
	{
		Vector2 a = diagram_vertices[hedge->a];
		Vector2 b = diagram_vertices[hedge->b];

		if (bounds.position.length_squared() == 0.0f && bounds.position.length_squared() == 0.0f) {
			bounds.position.x = a.x;
			bounds.position.y = a.y;
		} else
			bounds.expand_to(a);

		bounds.expand_to(b);

		Rect2 r = segment_to_rect(a, b).grow(1.0f);
		Rect2i rgrid = rect_to_grid(r);
		int x, y;
		for (y = 0; y < rgrid.size.y; y++) {
			for (x = 0; x < rgrid.size.x; x++) {
				int px = rgrid.position.x + x;
				int py = rgrid.position.y + y;
				Rect2 xr = get_grid_rect(px, py).grow(16.0f);
				if (segment_intersects_rect(a, b, xr))
					hedge_grid.insert_hedge_to_grid_cell(px, py, hedge);
			}
		}
	}
	inline int get_grid_x(float x) const
	{
		return (int)(x / grid_width);
	}
	inline int get_grid_y(float y) const
	{
		return (int)(y / grid_height);
	}
	float grid_width, grid_height;
	void sort_angle(Vector<int> &sort_data);
	void smooth_heights();
public:
	void build(Ref<Curve> curve, Ref<FastNoiseLite> noise);
	void draw_debug(Node *drawable, int size_x, int size_y) const;
	int find_edge(int a, int b);
	void setup_vshapes();
	inline const PoolVector<struct vshape> &get_vshapes() const
	{
		const PoolVector<struct vshape> &ret = vshapes;
		return ret;
	}
	inline PoolVector<struct vshape> &get_vshapes()
	{
		PoolVector<struct vshape> &ret = vshapes;
		return ret;
	}
	Vector2 get_influence(int x, int y, float radius) const;
	RoadGrid();
	~RoadGrid();
	inline int get_diagram_vertex_count() const
	{
		return diagram_vertices.size();
	}
	inline int get_map_hedges_count() const
	{
		return map_hedges.size();
	}
	void generate_3d_vertices(Ref<Curve> curve, Ref<FastNoiseLite> noise);
	void generate_building_positions();
	void generate_site_building_positions(const struct map_site *site);
	int get_site_from_point(int x, int z);
	inline bool site_is_town(int site) const
	{
		return map_sites[site].site_type == map_site::SITE_TOWN;
	}
	inline bool site_is_farm(int site) const
	{
		return map_sites[site].site_type == map_site::SITE_FARM;
	}
	inline float get_site_avg_height(int site) const
	{
		return map_sites[site].avg_height;
	}
	inline Vector2 get_site_pos(int site) const
	{
		return map_sites[site].pos;
	}
	HashMap<int, PoolVector<Vector2> > polygon_cache_2d;
	inline PoolVector<Vector2> get_site_polygon_2d(int site)
	{
		if (polygon_cache_2d.has(site))
			return polygon_cache_2d[site];
		if (map_sites.size() <= site)
			return PoolVector<Vector2>();
		int count = 0, i;
		int psize = map_sites[site].polygon_ind.size();
		PoolVector<Vector2> polygon;
		polygon.resize(psize);
		int prev = -1;
		for (i = 0; i < psize; i++) {
			int idx = map_sites[site].polygon_ind[i];
			if (idx == prev)
				continue;
			polygon.write()[count++] = diagram_vertices[idx];
			prev = idx;
		}
		polygon.resize(count);
		polygon_cache_2d[site] = polygon;
		return polygon;
	}
	HashMap<int, PoolVector<Vector3> > polygon_cache_3d;
	inline PoolVector<Vector3> get_site_polygon_3d(int site)
	{
		if (polygon_cache_3d.has(site))
			return polygon_cache_3d[site];
		if (map_sites.size() <= site)
			return PoolVector<Vector3>();
		int count = 0, i;
		int psize = map_sites[site].polygon_ind.size();
		PoolVector<Vector3> polygon;
		polygon.resize(psize);
		int prev = -1;
		for (i = 0; i < psize; i++) {
			int idx = map_sites[site].polygon_ind[i];
			if (idx == prev)
				continue;
			polygon.write()[count++] = vertices[idx];
			prev = idx;
		}
		polygon.resize(count);
		polygon_cache_3d[site] = polygon;
		return polygon;
	}
	inline PoolVector<int> get_here_sites(const Vector3 &position)
	{
		PoolVector<int> ret;
		int i;
		Rect2i xpos;
		xpos.position = Vector2i((int)position.x, (int)position.z);
		xpos.grow(300);
		for (i = 0; i < map_sites.size(); i++) {
			if (xpos.intersects(map_sites[i].rect))
				ret.push_back(i);
			if (xpos.encloses(map_sites[i].rect))
				ret.push_back(i);
		}
		return ret;
	}
	void save_json(const String &path);
	PoolVector<Vector3> get_site_border(int site);
	inline int get_site_count() const
	{
		return map_sites.size();
	}
	inline int get_site_type(int site) const
	{
		return map_sites[site].site_type;
	}
	PoolVector<Vector3> get_site_border(int site, float offt);
	PoolVector<Vector3> get_site_radial_points(int site, float bofft, float offt);
	Ref<AStar> get_astar() const
	{
		return astar;
	}
	inline int get_closest_point(Vector3 to_position, bool include_disabled=false) const
	{
		return astar->get_closest_point(to_position, include_disabled);
	}
	inline Vector3 get_closest_position_in_segment(Vector3 to_position) const
	{
		return astar->get_closest_position_in_segment(to_position);
	}
	inline PoolVector<Vector3> get_point_path(int p_from_id, int p_to_id)
	{
		return astar->get_point_path(p_from_id, p_to_id);
	}
	inline PoolVector<int> get_id_path(int p_from_id, int p_to_id)
	{
		return astar->get_id_path(p_from_id, p_to_id);
	}
	inline Vector3 get_point_position(int p_id) const
	{
		return astar->get_point_position(p_id);
	}
};
#endif
