// Copyright Marcus Del Favero 2025
// Licensed under the GNU AGPLv3 with an exception, see `README.md` for details
use std::{mem, iter};
use std::collections::BTreeMap;

use rand::seq::SliceRandom;
use rand_chacha::ChaCha20Rng;
use glam::Vec2;

use super::edge::Edge;
use assets::Polygon as OutPolygon;

#[derive(PartialEq, Eq)]
pub struct Polygon(Vec<Edge>);

pub enum Split<'a> {
	None, // Line isn't intersecting so no split
	Some([Polygon; 2]), // Line is intersecting with two edges, will split
	TooMany(Vec<&'a Edge>), // Line is intersecting with more than two edges (due to concavity), too lazy to write code to handle to handle that so don't split
}

pub enum ConcaveSplit {
	Convex(Polygon),
	Concave([Polygon; 2]),
	Fail, // Sometimes my algorithm cannot split the concave polygon (no vertex found), so indicate this case
}

impl Polygon {
	pub fn new_root() -> Polygon {
		Polygon::check(Polygon(vec![
			Edge(Vec2::new(-0.5, 0.5), Vec2::new(0.25, 0.375)),
			Edge(Vec2::new(0.25, 0.375), Vec2::new(0.5, 0.0)),
			Edge(Vec2::new(0.5, 0.0), Vec2::new(0.25, -0.375)),
			Edge(Vec2::new(0.25, -0.375), Vec2::new(-0.5, -0.5)),
			Edge(Vec2::new(-0.5, -0.5), Vec2::new(-0.25, 0.0)),
			Edge(Vec2::new(-0.25, 0.0), Vec2::new(-0.5, 0.5)),
		]))
	}

	// Checks all invariants
	fn check(poly: Polygon) -> Polygon {
		assert!(poly.0.len() >= 3, "Must have at least three edges");
		assert!(poly.0.first().unwrap().0 == poly.0.last().unwrap().1, "First vertex of first edge must be equal to the last vertex of last edge (it being a loop)");
		assert!(poly.0.iter().all(|e| e.0 != e.1), "No edges can be of zero length");
		for edges in poly.0.windows(2) {
			assert!(edges[0].1 == edges[1].0, "All edges must be connected");
		}
		poly
	}

	pub fn edges(&self) -> impl Iterator<Item = Edge> + '_ {
		self.0.iter().cloned()
	}

	pub fn split(&self, all_int: &BTreeMap<Edge, Vec2>) -> Split<'_> {
		let int = self.0.iter().filter(|edge| all_int.contains_key(edge)).collect::<Vec<_>>();
		match int.len() {
			0 => Split::None,
			2 => {
				assert_ne!(all_int[int[0]], all_int[int[1]], "Somehow intersecting the same point twice on two different edges, this shouldn't happen");

				let (mut a, mut b) = (Vec::new(), Vec::new());
				let mut poly = &mut a;

				let mut int_edge_found = false;
				for edge in &self.0 {
					match int.iter().position(|&i| i == edge) {
						Some(i) => {
							let int_point1 = all_int[int[i]];
							let int_point2 = all_int[int[1 - i]]; // Gets the other intersected edge

							#[allow(clippy::branches_sharing_code)] // Makes it more understandable
							if int_edge_found {
								// Here int_point1 and int_point2 are swapped from where they originally were in the first iteration
								poly.push(Edge(edge.0, int_point1)); // Finishes off the second polygon by connecting to the second intersection point

								poly = &mut a;
								poly.push(Edge(int_point1, edge.1)); // Connects the second intersecting point to the second vertex of that edge, after this the first polygon will be completed
							} else {
								// Connects the edge up to the intersection point and then the new edge between the intersection points
								poly.push(Edge(edge.0, int_point1));
								poly.push(Edge(int_point1, int_point2));

								// Then for the new polygon adds this new edge between the intersection points and then along the original edge
								poly = &mut b;
								poly.push(Edge(int_point2, int_point1));
								poly.push(Edge(int_point1, edge.1));
								int_edge_found = true;
							}
						}
						None => poly.push(edge.clone()),
					}
				}

				assert!(int_edge_found, "No intersecting edge found");

				Split::Some([
					Polygon::check(Polygon(a)),
					Polygon::check(Polygon(b)),
				])
			}
			_ => {
				/*
				 * If intersected more than two edges but an even number, then it's
				 * due to the polygon being concave. In that case, don't try to
				 * intersect and indicate that.
				 */
				if int.len() % 2 == 0 {
					Split::TooMany(int)
				} else { // This shouldn't happen, if it does panicking is better than silently failing as the former indicates my code is broken
					panic!("This shouldn't happen, t = 0 or 1 case should've excluded this before");
				}
			}
		}
	}

	pub fn split_if_concave(self, rng: &mut ChaCha20Rng) -> ConcaveSplit {
		let i = self.0.windows(2)
			.position(|edges| !Polygon::clockwise(&edges[0], &edges[1]))
			.map(|i| i + 1)
			.or_else(|| (!Polygon::clockwise(self.0.last().unwrap(), self.0.first().unwrap())).then_some(0));

		if let Some(i) = i {
			let mut other = {
				let i_prev = i.checked_sub(1).unwrap_or(self.0.len() - 1);
				let i_next = (i + 1) % self.0.len();
				(0..self.0.len()).filter(|&j| j != i && j != i_prev && j != i_next).collect::<Vec<_>>()
			};
			assert!(!other.is_empty());
			other.shuffle(rng);

			let vertices = self.into_vertices();

			for mut j in other {
				let mut i = i;

				assert!(i != j);
				if i > j { mem::swap(&mut i, &mut j); }

				let a = Polygon::into_edges(vertices[i..=j].to_vec());
				let b = Polygon::into_edges(vertices[0..=i].iter().chain(vertices[j..].iter()).copied().collect::<Vec<_>>());
				if a.is_convex() && b.is_convex() {
					return ConcaveSplit::Concave([a, b]);
				}
			}

			ConcaveSplit::Fail
		} else {
			ConcaveSplit::Convex(self)
		}
	}

	fn is_convex(&self) -> bool {
		self.0.windows(2).all(|edges| Polygon::clockwise(&edges[0], &edges[1])) && Polygon::clockwise(self.0.last().unwrap(), self.0.first().unwrap())
	}

	/**
	 * Determines whether the direction of edge `b` is clockwise of the
	 * direction of edge `a`.
	 *
	 * This can be thought of as taking the determinant of a matrix with column
	 * vectors being the directions of `b` and `a`. If the determinant is
	 * non-negative, it's considered clockwise, otherwise anti-clockwise.
	 */
	fn clockwise(a: &Edge, b: &Edge) -> bool {
		(b.1.x - b.0.x) * (a.1.y - a.0.y) >= (a.1.x - a.0.x) * (b.1.y - b.0.y)
	}

	pub fn into_vertices(self) -> Vec<Vec2> {
		self.0.into_iter().map(|e| e.0).collect()
	}

	fn into_edges(vertices: Vec<Vec2>) -> Polygon {
		Polygon::check(Polygon(vertices.windows(2).map(|v| Edge(v[0], v[1])).chain(iter::once(Edge(*vertices.last().unwrap(), *vertices.first().unwrap()))).collect::<Vec<_>>()))
	}

	pub fn into_output(self) -> OutPolygon {
		// Calculates the area and centre of mass using: https://en.wikipedia.org/wiki/Centroid#Of_a_polygon
		let mut vertices = self.into_vertices();
		vertices.push(*vertices.first().unwrap());
		let area = vertices.windows(2).map(|p| p[0].x * p[1].y - p[1].x * p[0].y).sum::<f32>() / 2.0;
		#[allow(clippy::suspicious_operation_groupings)] // Don't worry clippy, it's fine
		let pos = vertices.windows(2).map(|p| Vec2::new(
			(p[0].x + p[1].x) * (p[0].x * p[1].y - p[1].x * p[0].y),
			(p[0].y + p[1].y) * (p[0].x * p[1].y - p[1].x * p[0].y),
		)).sum::<Vec2>() / (6.0 * area);
		vertices.pop();
		OutPolygon { pos, size: area.abs().sqrt(), vertices }
	}
}

#[cfg(test)]
mod tests {
	use rand::SeedableRng;

	use super::*;

	#[test]
	fn root_concave() {
		assert!(!Polygon::new_root().is_convex());
	}

	#[test]
	fn triangles_convex() {
		for _ in 0..100 { // Some property-based testing
			let mut a = Vec2::new(rand::random::<f32>(), rand::random::<f32>());
			let mut b = Vec2::new(rand::random::<f32>(), rand::random::<f32>());
			let c = Vec2::new(rand::random::<f32>(), rand::random::<f32>());
			if !Polygon::clockwise(&Edge(a, b), &Edge(b, c)) {
				mem::swap(&mut a, &mut b);
			}
			assert!(Polygon::check(Polygon(vec![Edge(a, b), Edge(b, c), Edge(c, a)])).is_convex());
		}
	}

	#[test]
	fn some_convex() {
		assert!(Polygon::into_edges(vec![
			Vec2::new(0.0, 0.5),
			Vec2::new(5.0, 0.5),
			Vec2::new(5.0, -5.5),
			Vec2::new(-5.0, -5.5),
			Vec2::new(-5.0, 0.5),
		]).is_convex());

		assert!(Polygon::into_edges(vec![
			Vec2::new(1.0, 0.0),
			Vec2::new(0.0, -1.0),
			Vec2::new(-1.0, 0.0),
			Vec2::new(0.0, 1.0),
		]).is_convex());

		assert!(Polygon::into_edges(vec![
			Vec2::new(1.0, 0.0),
			Vec2::new(2.0, -1.0),
			Vec2::new(3.0, -2.1),
			Vec2::new(-2.0, 0.5),
		]).is_convex());
	}

	#[test]
	fn some_concave() {
		assert!(!Polygon::into_edges(vec![
			Vec2::new(0.0, 0.0),
			Vec2::new(1.0, 0.0),
			Vec2::new(1.0, 1.0),
			Vec2::new(2.0, -1.0),
		]).is_convex());

		assert!(!Polygon::into_edges(vec![
			Vec2::new(0.0, 0.0),
			Vec2::new(1.0, 1.0),
			Vec2::new(2.0, 0.0),
			Vec2::new(3.0, 1.0),
			Vec2::new(4.0, -1.0),
			Vec2::new(0.0, -1.0),
		]).is_convex());
	}

	#[test]
	fn should_split_root() {
		assert!(matches!(Polygon::new_root().split_if_concave(&mut ChaCha20Rng::seed_from_u64(0)), ConcaveSplit::Concave(_)));
	}

	#[test]
	fn cannot_split() {
		assert!(matches!(Polygon::into_edges(vec![
			Vec2::new(-0.26984113, 0.039682277),
			Vec2::new(-0.2578791, 0.048349734),
			Vec2::new(-0.24553189, 0.027325014),
			Vec2::new(-0.2517772, -0.013837641),
			Vec2::new(-0.25560063, -0.011201274),
			Vec2::new(-0.25, 0.0),
		]).split_if_concave(&mut ChaCha20Rng::seed_from_u64(0)), ConcaveSplit::Fail));
	}
}
