using System;
using System.Collections.Generic;
using Sandbox;

namespace RedSnail.WaterTool2;

/// <summary>
/// The coast zone: the water round the land, out to a distance from the coast, as a surface of its own (a lake turned
/// inside out, the land its holes). The infinite sea is masked out over it and over the land, and takes over past it.
/// <para>
/// It is laid on the very grid the sea's finest ring is drawn on, and every cell is split the same way, so its triangles
/// subdivide every ring's; its vertices take the sea's surface exactly as the rings draw it, so it is the sea's own
/// surface point for point and the two meet without a seam anywhere. Square tiles of that grid say what is where: the
/// open sea's (drawn by the rings), the coast zone's, or land's (nothing).
/// </para>
/// </summary>
internal sealed class CoastZone
{
	/// <summary>
	/// Grid cells along a tile's side: the zone is made of whole tiles.
	/// </summary>
	public const int TileCells = 16;

	/// <summary>
	/// Tiles along a chunk's side: the zone is drawn a chunk at a time.
	/// </summary>
	public const int ChunkTiles = 4;

	public const int ChunkCells = TileCells * ChunkTiles;

	/// <summary>
	/// Past this many tiles the zone is refused: the distance asked for is far too big for a surface of its own.
	/// </summary>
	private const int MaxTiles = 1 << 22;

	public enum TileKind : byte
	{
		/// <summary>
		/// The open sea: the infinite sea's own.
		/// </summary>
		Sea,

		/// <summary>
		/// Near the coast: the zone's surface covers its water.
		/// </summary>
		Coast,

		/// <summary>
		/// Inland: no water at all.
		/// </summary>
		Land
	}

	/// <summary>
	/// The grid's spacing: the sea's finest ring's cell size.
	/// </summary>
	public float Cell { get; }

	public float Tile => Cell * TileCells;

	/// <summary>
	/// The tile grid: the index of its first tile (tiles are counted from the world's origin) and how many tiles across.
	/// </summary>
	public int FirstTileX { get; }

	public int FirstTileY { get; }

	public int Width { get; }

	public int Height { get; }

	/// <summary>
	/// The sea's level in the world.
	/// </summary>
	public float SeaLevel { get; }

	private readonly TileKind[] m_Tiles;
	private readonly List<(Vector2 A, Vector2 B)> m_Segments;
	private readonly Dictionary<int, float[]> m_Rows;
	private HashSet<(int X, int Y)> m_CoastChunks;



	private CoastZone(float _Cell, int _FirstTileX, int _FirstTileY, int _Width, int _Height, float _SeaLevel, List<(Vector2 A, Vector2 B)> _Segments, Dictionary<int, float[]> _Rows)
	{
		Cell = _Cell;
		FirstTileX = _FirstTileX;
		FirstTileY = _FirstTileY;
		Width = _Width;
		Height = _Height;
		SeaLevel = _SeaLevel;

		m_Tiles = new TileKind[_Width * _Height];
		m_Segments = _Segments;
		m_Rows = _Rows;
	}



	/// <summary>
	/// The zone round a set of coastlines (closed loops round land, in plan, in the world): every tile within
	/// <paramref name="_Distance"/> of a coast is the zone's, every other tile on land is land. The blocks river mouths
	/// are built in are not part of it: they are laid over it (see <see cref="IsMasked"/>), so a mouth moving never
	/// rebuilds the zone. Null when there is no coastline, or the zone would be far too big.
	/// </summary>
	public static CoastZone Build(IReadOnlyList<Vector2[]> _Coasts, float _Cell, float _Distance, float _SeaLevel)
	{
		var segments = new List<(Vector2 A, Vector2 B)>();
		var min = new Vector2(float.MaxValue, float.MaxValue);
		var max = new Vector2(float.MinValue, float.MinValue);

		foreach (var loop in _Coasts)
		{
			if (loop is null || loop.Length < 3)
				continue;

			for (int e = 0; e < loop.Length; e++)
			{
				Vector2 a = loop[e];

				segments.Add((a, loop[(e + 1) % loop.Length]));
				min = new Vector2(MathF.Min(min.x, a.x), MathF.Min(min.y, a.y));
				max = new Vector2(MathF.Max(max.x, a.x), MathF.Max(max.y, a.y));
			}
		}

		if (segments.Count == 0)
			return null;

		float cell = MathF.Max(1.0f, _Cell);
		float tile = cell * TileCells;
		float reach = MathF.Max(0.0f, _Distance);

		int firstX = (int)MathF.Floor((min.x - reach) / tile) - 1;
		int firstY = (int)MathF.Floor((min.y - reach) / tile) - 1;
		int lastX = (int)MathF.Floor((max.x + reach) / tile) + 1;
		int lastY = (int)MathF.Floor((max.y + reach) / tile) + 1;

		long tiles = (long)(lastX - firstX + 1) * (lastY - firstY + 1);

		if (tiles > MaxTiles)
			return null;

		// Where every grid row crosses the coastlines, for "which side of the coast is this point on".
		var crossings = new Dictionary<int, List<float>>();

		foreach (var (a, b) in segments)
		{
			if (a.y == b.y)
				continue;

			// The rows in [low, high): a row through a corner counts it once.
			float low = MathF.Min(a.y, b.y);
			float high = MathF.Max(a.y, b.y);
			int first = (int)MathF.Ceiling(low / cell);
			int last = (int)MathF.Ceiling(high / cell) - 1;

			for (int j = first; j <= last; j++)
			{
				float y = j * cell;

				if (!crossings.TryGetValue(j, out var row))
				{
					row = new List<float>();
					crossings[j] = row;
				}

				row.Add(a.x + (y - a.y) * (b.x - a.x) / (b.y - a.y));
			}
		}

		var rows = new Dictionary<int, float[]>(crossings.Count);

		foreach (var (j, row) in crossings)
		{
			row.Sort();
			rows[j] = row.ToArray();
		}

		var zone = new CoastZone(cell, firstX, firstY, lastX - firstX + 1, lastY - firstY + 1, _SeaLevel, segments, rows);

		// Near the coast: every tile within the distance of an edge of it.
		foreach (var (a, b) in segments)
		{
			int x0 = (int)MathF.Floor((MathF.Min(a.x, b.x) - reach) / tile);
			int x1 = (int)MathF.Floor((MathF.Max(a.x, b.x) + reach) / tile);
			int y0 = (int)MathF.Floor((MathF.Min(a.y, b.y) - reach) / tile);
			int y1 = (int)MathF.Floor((MathF.Max(a.y, b.y) + reach) / tile);

			for (int y = y0; y <= y1; y++)
			{
				for (int x = x0; x <= x1; x++)
					zone.SetTile(x, y, TileKind.Coast);
			}
		}

		// Further inland, land: a tile is wholly on one side of the coast there, so its middle says which.
		for (int y = 0; y < zone.Height; y++)
		{
			for (int x = 0; x < zone.Width; x++)
			{
				int tileX = zone.FirstTileX + x;
				int tileY = zone.FirstTileY + y;

				if (zone.TileAt(tileX, tileY) == TileKind.Sea && zone.IsLand(tileX * TileCells + TileCells / 2, tileY * TileCells + TileCells / 2))
					zone.SetTile(tileX, tileY, TileKind.Land);
			}
		}

		return zone;
	}



	public TileKind TileAt(int _X, int _Y)
	{
		int x = _X - FirstTileX;
		int y = _Y - FirstTileY;

		if (x < 0 || y < 0 || x >= Width || y >= Height)
			return TileKind.Sea;

		return m_Tiles[y * Width + x];
	}



	private void SetTile(int _X, int _Y, TileKind _Kind)
	{
		int x = _X - FirstTileX;
		int y = _Y - FirstTileY;

		if (x < 0 || y < 0 || x >= Width || y >= Height)
			return;

		m_Tiles[y * Width + x] = _Kind;
	}



	/// <summary>
	/// The tile a world point (in plan) is in.
	/// </summary>
	public (int X, int Y) TileOf(Vector2 _World)
	{
		return ((int)MathF.Floor(_World.x / Tile), (int)MathF.Floor(_World.y / Tile));
	}



	/// <summary>
	/// Whether the infinite sea is masked out at a world point (in plan): the coast zone's surface is there instead, or
	/// land, or a river mouth (<paramref name="_Mouths"/>, the tiles their blocks take). Mirrors InsideCoastZone in the
	/// water shader.
	/// </summary>
	public bool IsMasked(Vector2 _World, IReadOnlySet<(int X, int Y)> _Mouths)
	{
		var tile = TileOf(_World);

		return TileAt(tile.X, tile.Y) != TileKind.Sea || _Mouths.Contains(tile);
	}



	/// <summary>
	/// The mask the shader reads: one value per tile, row after row, 1 where the infinite sea is masked out (the zone,
	/// the land, and the river mouths' blocks laid over them), over the zone's tiles grown to take in every mouth.
	/// </summary>
	public float[] MaskValues(IReadOnlySet<(int X, int Y)> _Mouths, out int _FirstX, out int _FirstY, out int _Width, out int _Height)
	{
		int firstX = FirstTileX;
		int firstY = FirstTileY;
		int lastX = FirstTileX + Width - 1;
		int lastY = FirstTileY + Height - 1;

		foreach (var (x, y) in _Mouths)
		{
			firstX = Math.Min(firstX, x);
			firstY = Math.Min(firstY, y);
			lastX = Math.Max(lastX, x);
			lastY = Math.Max(lastY, y);
		}

		_FirstX = firstX;
		_FirstY = firstY;
		_Width = lastX - firstX + 1;
		_Height = lastY - firstY + 1;

		var values = new float[_Width * _Height];

		for (int y = 0; y < _Height; y++)
		{
			for (int x = 0; x < _Width; x++)
			{
				var tile = (firstX + x, firstY + y);

				if (TileAt(tile.Item1, tile.Item2) != TileKind.Sea || _Mouths.Contains(tile))
					values[y * _Width + x] = 1.0f;
			}
		}

		return values;
	}



	/// <summary>
	/// The chunks that have some of the zone's water to draw. Worked out once: the zone never changes.
	/// </summary>
	public IReadOnlyCollection<(int X, int Y)> CoastChunks()
	{
		if (m_CoastChunks is not null)
			return m_CoastChunks;

		m_CoastChunks = new HashSet<(int X, int Y)>();

		for (int y = 0; y < Height; y++)
		{
			for (int x = 0; x < Width; x++)
			{
				if (m_Tiles[y * Width + x] == TileKind.Coast)
					m_CoastChunks.Add((FloorDiv(FirstTileX + x, ChunkTiles), FloorDiv(FirstTileY + y, ChunkTiles)));
			}
		}

		return m_CoastChunks;
	}



	/// <summary>
	/// What a chunk is made of, for its signature: the kind of each of its tiles, and which are left to river mouths.
	/// </summary>
	public void AddChunkToHash(ref StableHash _Hash, int _ChunkX, int _ChunkY, IReadOnlySet<(int X, int Y)> _Excluded)
	{
		for (int ty = 0; ty < ChunkTiles; ty++)
		{
			for (int tx = 0; tx < ChunkTiles; tx++)
			{
				int x = _ChunkX * ChunkTiles + tx;
				int y = _ChunkY * ChunkTiles + ty;

				_Hash.Add((int)TileAt(x, y));
				_Hash.Add(_Excluded.Contains((x, y)));
			}
		}
	}



	/// <summary>
	/// The outline of the masked area (coast zone and land against the open sea), as edges in the world, in plan.
	/// </summary>
	public IEnumerable<(Vector2 A, Vector2 B)> MaskOutline(IReadOnlySet<(int X, int Y)> _Mouths)
	{
		float tile = Tile;

		bool Masked(int _X, int _Y)
		{
			return TileAt(_X, _Y) != TileKind.Sea || _Mouths.Contains((_X, _Y));
		}

		int firstX = FirstTileX;
		int firstY = FirstTileY;
		int lastX = FirstTileX + Width - 1;
		int lastY = FirstTileY + Height - 1;

		foreach (var (x, y) in _Mouths)
		{
			firstX = Math.Min(firstX, x);
			firstY = Math.Min(firstY, y);
			lastX = Math.Max(lastX, x);
			lastY = Math.Max(lastY, y);
		}

		for (int y = firstY; y <= lastY; y++)
		{
			for (int x = firstX; x <= lastX; x++)
			{
				if (!Masked(x, y))
					continue;

				if (!Masked(x - 1, y))
					yield return (new Vector2(x * tile, y * tile), new Vector2(x * tile, (y + 1) * tile));

				if (!Masked(x + 1, y))
					yield return (new Vector2((x + 1) * tile, y * tile), new Vector2((x + 1) * tile, (y + 1) * tile));

				if (!Masked(x, y - 1))
					yield return (new Vector2(x * tile, y * tile), new Vector2((x + 1) * tile, y * tile));

				if (!Masked(x, y + 1))
					yield return (new Vector2(x * tile, (y + 1) * tile), new Vector2((x + 1) * tile, (y + 1) * tile));
			}
		}
	}



	/// <summary>
	/// Whether a grid point (counted in cells from the world's origin) is on land: inside an odd number of coastlines.
	/// </summary>
	public bool IsLand(int _I, int _J)
	{
		if (!m_Rows.TryGetValue(_J, out var row))
			return false;

		float x = _I * Cell;
		int low = 0;
		int high = row.Length;

		// How many crossings lie left of the point.
		while (low < high)
		{
			int middle = (low + high) >> 1;

			if (row[middle] < x)
				low = middle + 1;
			else
				high = middle;
		}

		return (low & 1) == 1;
	}



	/// <summary>
	/// The zone's surface over one chunk, in the world: the water of its coast tiles (all but those left to river
	/// mouths), cell by cell. A cell at sea is the sea's two triangles, split as the rings split theirs; a cell the coast
	/// crosses keeps its part at sea, cut along the coast. Null when the chunk has no water.
	/// </summary>
	public WaterMeshData BuildChunk(int _ChunkX, int _ChunkY, IReadOnlySet<(int X, int Y)> _Excluded)
	{
		const int side = ChunkCells + 1;

		int i0 = _ChunkX * ChunkCells;
		int j0 = _ChunkY * ChunkCells;
		float clamp = Cell * 2.0f;

		// Which side of the coast every grid point of the chunk is on (sea positive), and how far from it the points near
		// it are, so the coast is cut where it really runs.
		var field = new float[side * side];

		for (int j = 0; j < side; j++)
		{
			for (int i = 0; i < side; i++)
				field[j * side + i] = IsLand(i0 + i, j0 + j) ? -clamp : clamp;
		}

		float minX = i0 * Cell - clamp;
		float minY = j0 * Cell - clamp;
		float maxX = (i0 + ChunkCells) * Cell + clamp;
		float maxY = (j0 + ChunkCells) * Cell + clamp;

		foreach (var (a, b) in m_Segments)
		{
			if (MathF.Max(a.x, b.x) < minX || MathF.Min(a.x, b.x) > maxX || MathF.Max(a.y, b.y) < minY || MathF.Min(a.y, b.y) > maxY)
				continue;

			int x0 = Math.Max(0, (int)MathF.Floor((MathF.Min(a.x, b.x) - clamp) / Cell) - i0);
			int x1 = Math.Min(side - 1, (int)MathF.Ceiling((MathF.Max(a.x, b.x) + clamp) / Cell) - i0);
			int y0 = Math.Max(0, (int)MathF.Floor((MathF.Min(a.y, b.y) - clamp) / Cell) - j0);
			int y1 = Math.Min(side - 1, (int)MathF.Ceiling((MathF.Max(a.y, b.y) + clamp) / Cell) - j0);

			for (int y = y0; y <= y1; y++)
			{
				for (int x = x0; x <= x1; x++)
				{
					int index = y * side + x;
					var point = new Vector2((i0 + x) * Cell, (j0 + y) * Cell);
					float distance = MathF.Max(0.001f, DistanceToSegment(point, a, b));

					if (distance < MathF.Abs(field[index]))
						field[index] = field[index] < 0.0f ? -distance : distance;
				}
			}
		}

		var mesher = new ChunkMesher(this, field, side, i0, j0);

		for (int ty = 0; ty < ChunkTiles; ty++)
		{
			for (int tx = 0; tx < ChunkTiles; tx++)
			{
				int tileX = _ChunkX * ChunkTiles + tx;
				int tileY = _ChunkY * ChunkTiles + ty;

				if (TileAt(tileX, tileY) != TileKind.Coast || _Excluded.Contains((tileX, tileY)))
					continue;

				for (int cj = 0; cj < TileCells; cj++)
				{
					for (int ci = 0; ci < TileCells; ci++)
						mesher.Cell(tx * TileCells + ci, ty * TileCells + cj);
				}
			}
		}

		return mesher.Finish();
	}



	private static float DistanceToSegment(Vector2 _Point, Vector2 _A, Vector2 _B)
	{
		Vector2 span = _B - _A;
		float lengthSquared = span.LengthSquared;
		float t = lengthSquared > 0.0f ? Math.Clamp(Vector2.Dot(_Point - _A, span) / lengthSquared, 0.0f, 1.0f) : 0.0f;

		return (_A + span * t).Distance(_Point);
	}



	private static int FloorDiv(int _A, int _B)
	{
		return _A >= 0 ? _A / _B : -((-_A + _B - 1) / _B);
	}



	/// <summary>
	/// Marching squares over one chunk's grid, sharing every corner and every crossing between the cells that meet there.
	/// </summary>
	private sealed class ChunkMesher
	{
		private readonly CoastZone m_Zone;
		private readonly float[] m_Field;
		private readonly int m_Side;
		private readonly int m_I0;
		private readonly int m_J0;

		private readonly List<Vector3> m_Positions = new();
		private readonly List<int> m_Indices = new();
		private readonly int[] m_Corners;
		private readonly Dictionary<int, int> m_Crossings = new();
		private readonly List<int> m_Polygon = new(8);



		public ChunkMesher(CoastZone _Zone, float[] _Field, int _Side, int _I0, int _J0)
		{
			m_Zone = _Zone;
			m_Field = _Field;
			m_Side = _Side;
			m_I0 = _I0;
			m_J0 = _J0;

			m_Corners = new int[_Side * _Side];

			for (int i = 0; i < m_Corners.Length; i++)
				m_Corners[i] = -1;
		}



		/// <summary>
		/// One cell, its corner at grid point (i, j) of the chunk.
		/// </summary>
		public void Cell(int _I, int _J)
		{
			int c00 = _J * m_Side + _I;
			int c10 = c00 + 1;
			int c01 = c00 + m_Side;
			int c11 = c01 + 1;

			bool s00 = m_Field[c00] > 0.0f;
			bool s10 = m_Field[c10] > 0.0f;
			bool s11 = m_Field[c11] > 0.0f;
			bool s01 = m_Field[c01] > 0.0f;

			if (s00 && s10 && s11 && s01)
			{
				// Split from its (1, 0) corner to its (0, 1) corner, as the rings split their cells.
				Triangle(Corner(c00), Corner(c10), Corner(c01));
				Triangle(Corner(c10), Corner(c11), Corner(c01));
				return;
			}

			if (!s00 && !s10 && !s11 && !s01)
				return;

			// Round the cell counter-clockwise: the corners at sea, and where the coast crosses each side.
			Span4 corners = new(c00, c10, c11, c01);
			Span4 sides = new(Horizontal(c00), Vertical(c10), Horizontal(c01), Vertical(c00));
			bool saddle = s00 == s11 && s10 == s01 && s00 != s10;

			// A saddle whose middle is land is two separate corners of sea.
			if (saddle && m_Field[c00] + m_Field[c10] + m_Field[c11] + m_Field[c01] <= 0.0f)
			{
				for (int k = 0; k < 4; k++)
				{
					if (m_Field[corners[k]] <= 0.0f)
						continue;

					Triangle(Corner(corners[k]), Crossing(sides[k]), Crossing(sides[(k + 3) % 4]));
				}

				return;
			}

			m_Polygon.Clear();

			for (int k = 0; k < 4; k++)
			{
				bool here = m_Field[corners[k]] > 0.0f;
				bool next = m_Field[corners[(k + 1) % 4]] > 0.0f;

				if (here)
					m_Polygon.Add(Corner(corners[k]));

				if (here != next)
					m_Polygon.Add(Crossing(sides[k]));
			}

			// The part of a square on one side of a line, or a saddle joined through its middle: convex either way.
			for (int k = 1; k + 1 < m_Polygon.Count; k++)
				Triangle(m_Polygon[0], m_Polygon[k], m_Polygon[k + 1]);
		}



		private void Triangle(int _A, int _B, int _C)
		{
			m_Indices.Add(_A);
			m_Indices.Add(_B);
			m_Indices.Add(_C);
		}



		private int Corner(int _Point)
		{
			if (m_Corners[_Point] >= 0)
				return m_Corners[_Point];

			int i = _Point % m_Side;
			int j = _Point / m_Side;

			m_Corners[_Point] = m_Positions.Count;
			m_Positions.Add(new Vector3((m_I0 + i) * m_Zone.Cell, (m_J0 + j) * m_Zone.Cell, m_Zone.SeaLevel));

			return m_Corners[_Point];
		}



		/// <summary>
		/// A side of a cell, as the grid edge from a point to the next one along (key even) or up (key odd).
		/// </summary>
		private static int Horizontal(int _Point)
		{
			return _Point * 2;
		}



		private static int Vertical(int _Point)
		{
			return _Point * 2 + 1;
		}



		/// <summary>
		/// Where the coast crosses a grid edge, worked out from the edge's own two ends whichever cell asks, so cells on
		/// either side of it (in this chunk or the next) share the very same point.
		/// </summary>
		private int Crossing(int _Edge)
		{
			if (m_Crossings.TryGetValue(_Edge, out int index))
				return index;

			int from = _Edge / 2;
			int to = (_Edge & 1) == 1 ? from + m_Side : from + 1;

			float a = m_Field[from];
			float b = m_Field[to];
			float t = Math.Clamp(a / (a - b), 0.001f, 0.999f);

			Vector3 start = Position(from);
			Vector3 end = Position(to);

			index = m_Positions.Count;
			m_Positions.Add(Vector3.Lerp(start, end, t));
			m_Crossings[_Edge] = index;

			return index;
		}



		private Vector3 Position(int _Point)
		{
			int i = _Point % m_Side;
			int j = _Point / m_Side;

			return new Vector3((m_I0 + i) * m_Zone.Cell, (m_J0 + j) * m_Zone.Cell, m_Zone.SeaLevel);
		}



		public WaterMeshData Finish()
		{
			if (m_Indices.Count == 0)
				return null;

			var mesh = new WaterMeshData(m_Positions.Count);

			for (int i = 0; i < m_Positions.Count; i++)
			{
				mesh.Positions[i] = m_Positions[i];
				mesh.SeaBlend[i] = 1.0f;
			}

			// Built in the world already.
			mesh.Finish(new Transform(Vector3.Zero), m_Indices);

			return mesh;
		}
	}



	/// <summary>
	/// Four ints, indexable, without an allocation per cell.
	/// </summary>
	private readonly struct Span4
	{
		private readonly int m_A;
		private readonly int m_B;
		private readonly int m_C;
		private readonly int m_D;



		public Span4(int _A, int _B, int _C, int _D)
		{
			m_A = _A;
			m_B = _B;
			m_C = _C;
			m_D = _D;
		}



		public int this[int _Index] => _Index switch
		{
			0 => m_A,
			1 => m_B,
			2 => m_C,
			_ => m_D
		};
	}
}