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

namespace Sunless.Architecture;

// One piece's edge, kept whole so an adjacency can be MEASURED rather than taken from the line it hashed to.
readonly struct ArchCarveEdge
{
	public ArchCarvePiece Piece { get; init; }
	public int Index { get; init; }
	public Vector2 From { get; init; }
	public Vector2 To { get; init; }
	public float Low { get; init; }
	public float High { get; init; }
	// The line it hashed to, kept rather than re-derived: the adjacency scan asked for it a second time per edge.
	public (long, long, long) Line { get; init; }
}

// One stretch of an edge; a T-junction or a neighbour change splits an edge into several.
readonly struct ArchCarveTouch
{
	public ArchCarvePiece Piece { get; init; }
	public float From { get; init; }
	public float To { get; init; }
}

sealed class ArchCarvePiece
{
	public List<Vector2> Loop { get; init; }
	public Vector2 Centre { get; init; }
	public Vector2 Min { get; init; }
	public Vector2 Max { get; init; }

	public ArchCarveBands Whole { get; set; }
	public ArchCarveBands Standing { get; set; }
	public List<ArchCarveTouch>[] Beside { get; set; }
}

sealed class ArchCarveGrid
{
	public List<ArchCarvePiece> Pieces { get; init; } = new();

	// The arrangement's one vertex table. Nothing finer than the finest unit the tool can author is a coordinate:
	// it is arithmetic. A grid line and a slanted crossing reaching one corner from different directions land a
	// tenth of an inch apart, and so do the same station measured along two different edges - and that tenth of
	// an inch is a sliver nobody owns, which is a hole where it is dropped and an overlapping wall where it is
	// not. So EVERY point that gets manufactured on an edge - a cell corner, a flank's stretch, a cap's station -
	// comes back through here and lands on the vertex its neighbour already claimed. This is the merge every
	// boolean runs after clipping; the difference is that a carve can run it before anything reads adjacency.
	readonly Dictionary<(long, long), Vector2> claimed = new();

	public const float WeldReach = ArchGridService.FinestSize;

	public Vector2 Welded( Vector2 point )
	{
		var cell = ((long)MathF.Floor( point.x / WeldReach ), (long)MathF.Floor( point.y / WeldReach ));

		for ( var dx = -1; dx <= 1; dx++ )
		{
			for ( var dy = -1; dy <= 1; dy++ )
			{
				if ( claimed.TryGetValue( (cell.Item1 + dx, cell.Item2 + dy), out var held ) && (held - point).Length < WeldReach )
				{
					return held;
				}
			}
		}

		claimed[cell] = point;

		return point;
	}
}

static class ArchCarveFrame
{
	public static Vector2 Turn( Vector2 point, float yaw )
	{
		if ( yaw == 0f )
		{
			return point;
		}

		var radians = yaw.DegreeToRadian();
		var sin = MathF.Sin( radians );
		var cos = MathF.Cos( radians );

		return new Vector2( point.x * cos - point.y * sin, point.x * sin + point.y * cos );
	}

	public static Vector3 Turn( Vector3 point, float yaw )
	{
		var flat = Turn( new Vector2( point.x, point.y ), yaw );

		return new Vector3( flat.x, flat.y, point.z );
	}

	// Orthogonal: turning the origin and the fall leaves every height the plane answers unchanged.
	public static ArchCarvePlane Turn( ArchCarvePlane plane, float yaw )
	{
		return new ArchCarvePlane
		{
			Datum = plane.Datum,
			Origin = Turn( plane.Origin, yaw ),
			Fall = Turn( plane.Fall, yaw )
		};
	}

	public static ArchCarveCell Turn( ArchCarveCell cell, float yaw )
	{
		var loop = cell.Loop.Select( point => Turn( point, yaw ) ).ToList();

		ArchFootprint.Bounds( loop, out var min, out var max );

		return new ArchCarveCell
		{
			Min = min,
			Max = max,
			Centre = Turn( cell.Centre, yaw ),
			Loop = loop,
			From = cell.From,
			To = cell.To,
			Foot = Turn( cell.Foot, yaw ),
			Head = Turn( cell.Head, yaw )
		};
	}
}

// The arrangement every carve is read off: pieces that tile the volumes and never straddle one's boundary, each
// knowing the neighbours it shares an edge with, end for end.
static partial class ArchCarveCells
{
	public static ArchCarveGrid Over( IReadOnlyList<ArchCarveVolume> volumes )
	{
		var grid = new ArchCarveGrid();
		var loops = Fewest( volumes );

		Weld( grid, loops );

		foreach ( var loop in loops )
		{
			var tidied = Tidied( loop );

			if ( Real( tidied ) )
			{
				grid.Pieces.Add( Piece( tidied ) );
			}
		}

		Link( grid.Pieces );

		return grid;
	}

	// Both arrangements are exact, so the choice between them is topology, and the ring wins whenever it holds:
	// its pieces meet edge for edge, so each one is a FOUR CORNERED face, while a sweep's pieces meet the next
	// slab's several and carry that slab's stations along the edge between them. Four true quads round a hole
	// beats eight rectangles that each have a vertex sitting in the middle of a side - which is the whole reason
	// the ring chords corner to corner rather than slabbing straight across.
	static List<List<Vector2>> Fewest( IReadOnlyList<ArchCarveVolume> volumes )
	{
		return ArchCarveQuads.Ring( volumes ) ?? Swept( volumes );
	}

	static void Weld( ArchCarveGrid grid, List<List<Vector2>> loops )
	{
		foreach ( var loop in loops )
		{
			for ( var index = 0; index < loop.Count; index++ )
			{
				loop[index] = grid.Welded( loop[index] );
			}
		}
	}

	// Welding lands neighbouring corners on each other, which leaves a loop carrying the same point twice.
	static List<Vector2> Tidied( List<Vector2> loop )
	{
		var kept = new List<Vector2>();

		foreach ( var point in loop )
		{
			Push( kept, point );
		}

		return kept;
	}

	static ArchCarvePiece Piece( List<Vector2> loop )
	{
		ArchFootprint.Bounds( loop, out var min, out var max );

		var centre = Vector2.Zero;

		foreach ( var point in loop )
		{
			centre += point;
		}

		return new ArchCarvePiece
		{
			Loop = loop,
			// Centroid, not bounds centre - a thin wedge's box centre can lie outside the wedge itself.
			Centre = centre / loop.Count,
			Min = min,
			Max = max
		};
	}

	// Matched per stretch, not whole edges - end for end would force every cut line grid-wide.
	static void Link( List<ArchCarvePiece> pieces )
	{
		var edges = new List<ArchCarveEdge>();
		var lines = new Dictionary<(long, long, long), List<int>>();

		foreach ( var piece in pieces )
		{
			piece.Beside = new List<ArchCarveTouch>[piece.Loop.Count];

			for ( var index = 0; index < piece.Loop.Count; index++ )
			{
				piece.Beside[index] = new List<ArchCarveTouch>();

				var from = piece.Loop[index];
				var to = piece.Loop[(index + 1) % piece.Loop.Count];
				var line = Line( from, to );

				if ( !lines.TryGetValue( line.Key, out var along ) )
				{
					along = new List<int>();
					lines[line.Key] = along;
				}

				along.Add( edges.Count );

				edges.Add( new ArchCarveEdge
				{
					Piece = piece,
					Index = index,
					From = from,
					To = to,
					Low = Vector2.Dot( from, line.Along ),
					High = Vector2.Dot( to, line.Along ),
					Line = line.Key
				} );
			}
		}

		// The bucket NEXT DOOR as well as this one. The key is a rounded direction and offset, so two edges lying
		// on one line can straddle a rounding boundary and land in different buckets - never compared, both sides
		// then read as the outside of the solid and each skins its own wall across the seam they share.
		for ( var index = 0; index < edges.Count; index++ )
		{
			foreach ( var beside in Nearby( lines, edges[index].Line ) )
			{
				if ( beside > index )
				{
					Touch( edges[index], edges[beside] );
				}
			}
		}
	}

	static IEnumerable<int> Nearby( Dictionary<(long, long, long), List<int>> lines, (long, long, long) key )
	{
		for ( var along = -1L; along <= 1L; along++ )
		{
			for ( var across = -1L; across <= 1L; across++ )
			{
				for ( var offset = -1L; offset <= 1L; offset++ )
				{
					if ( lines.TryGetValue( (key.Item1 + along, key.Item2 + across, key.Item3 + offset), out var held ) )
					{
						foreach ( var index in held )
						{
							yield return index;
						}
					}
				}
			}
		}
	}

	static void Touch( ArchCarveEdge left, ArchCarveEdge right )
	{
		if ( ReferenceEquals( left.Piece, right.Piece ) || !Shares( left, right ) )
		{
			return;
		}

		var low = MathF.Max( MathF.Min( left.Low, left.High ), MathF.Min( right.Low, right.High ) );
		var high = MathF.Min( MathF.Max( left.Low, left.High ), MathF.Max( right.Low, right.High ) );

		if ( high - low < ArchCarve.Grain )
		{
			return;
		}

		left.Piece.Beside[left.Index].Add( Stretch( left, right.Piece, low, high ) );
		right.Piece.Beside[right.Index].Add( Stretch( right, left.Piece, low, high ) );
	}

	// The line key is a HASH of a normalised direction, so it can only PROPOSE a shared line - two cuts turned a
	// degree apart quantise into one bucket. Matched on the strength of that, a cell closes its seam against a
	// piece it never touches and both sides then skin their own wall across the same span, which is a face
	// standing inside the solid. So the edges are measured: truly collinear, and the two pieces on opposite
	// sides of them, because a neighbour lies ACROSS an edge and never along it.
	static bool Shares( ArchCarveEdge left, ArchCarveEdge right )
	{
		return MathF.Abs( Cross( left.From, left.To, right.From ) ) < ArchCarve.Grain
			&& MathF.Abs( Cross( left.From, left.To, right.To ) ) < ArchCarve.Grain;
	}

	// Overlap measured along the canonical line direction, so fractions arrive swapped and must be ordered.
	static ArchCarveTouch Stretch( ArchCarveEdge edge, ArchCarvePiece beside, float low, float high )
	{
		var first = Fraction( edge, low );
		var second = Fraction( edge, high );

		return new ArchCarveTouch
		{
			Piece = beside,
			From = MathF.Min( first, second ),
			To = MathF.Max( first, second )
		};
	}

	static float Fraction( ArchCarveEdge edge, float at )
	{
		var span = edge.High - edge.Low;

		return MathF.Abs( span ) < ArchCarve.Grain ? 0f : Math.Clamp( (at - edge.Low) / span, 0f, 1f );
	}

	static ((long, long, long) Key, Vector2 Along) Line( Vector2 from, Vector2 to )
	{
		var along = (to - from).Normal;

		// One canonical direction per line, or the two sides land in different groups.
		if ( along.x < -0.0001f || MathF.Abs( along.x ) < 0.0001f && along.y < 0f )
		{
			along = -along;
		}

		var normal = new Vector2( -along.y, along.x );
		var offset = Vector2.Dot( normal, from );

		return ((Grained( along.x ), Grained( along.y ), Grained( offset )), along);
	}

	static long Grained( float value ) => (long)MathF.Round( value / ArchCarve.Grain );

	static (long, long) Quantised( Vector2 point )
	{
		return ((long)MathF.Round( point.x / ArchCarve.Grain ), (long)MathF.Round( point.y / ArchCarve.Grain ));
	}

	static void Push( List<Vector2> loop, Vector2 point )
	{
		if ( loop.Count > 0 && (loop[^1] - point).Length < ArchCarve.Grain )
		{
			return;
		}

		if ( loop.Count > 1 && (loop[0] - point).Length < ArchCarve.Grain )
		{
			return;
		}

		loop.Add( point );
	}

	// How far off the line the point is, as a DISTANCE - the tolerance the clip compares against.
	static float Cross( Vector2 a, Vector2 b, Vector2 point )
	{
		var span = b - a;
		var length = span.Length;

		if ( length < 0.0001f )
		{
			return 0f;
		}

		return (span.x * (point.y - a.y) - span.y * (point.x - a.x)) / length;
	}

	// Thinner than the grain in its narrow direction is clip noise, not geometry.
	static bool Real( List<Vector2> loop )
	{
		if ( loop.Count < 3 )
		{
			return false;
		}

		var area = MathF.Abs( ArchFootprint.SignedArea( loop ) );
		var longest = 0f;

		for ( var index = 0; index < loop.Count; index++ )
		{
			longest = MathF.Max( longest, (loop[(index + 1) % loop.Count] - loop[index]).Length );
		}

		return longest > ArchCarve.Grain && area / longest > ArchCarve.Grain;
	}

	// Walked off the arrangement itself - exact for angled pieces, where bounding-rect unions square off notches.
	public static List<List<Vector2>> Boundary( IEnumerable<ArchCarvePiece> pieces, float height )
	{
		var standing = pieces.Where( piece => Holds( piece, height ) ).ToHashSet();
		var next = new Dictionary<(long, long), List<Vector2>>();

		foreach ( var piece in standing )
		{
			for ( var index = 0; index < piece.Loop.Count; index++ )
			{
				if ( piece.Beside[index].Any( touch => standing.Contains( touch.Piece ) ) )
				{
					continue;
				}

				var from = piece.Loop[index];
				var to = piece.Loop[(index + 1) % piece.Loop.Count];

				if ( !next.TryGetValue( Quantised( from ), out var ends ) )
				{
					ends = new List<Vector2>();
					next[Quantised( from )] = ends;
				}

				ends.Add( to );
			}
		}

		var loops = new List<List<Vector2>>();

		while ( next.Count > 0 )
		{
			var start = next.Keys.First();
			var loop = new List<Vector2>();
			var at = start;

			while ( next.TryGetValue( at, out var ends ) && ends.Count > 0 )
			{
				var step = ends[0];

				ends.RemoveAt( 0 );

				if ( ends.Count == 0 )
				{
					next.Remove( at );
				}

				loop.Add( step );
				at = Quantised( step );

				if ( at == start )
				{
					break;
				}
			}

			var kept = Straightened( loop );

			if ( kept.Count >= 3 )
			{
				loops.Add( kept );
			}
		}

		return loops;
	}

	static bool Holds( ArchCarvePiece piece, float height )
	{
		return piece.Standing.Spans.Any( span => height > span.From - ArchCarve.Grain && height < span.To + ArchCarve.Grain );
	}

	static List<Vector2> Straightened( List<Vector2> loop )
	{
		var kept = new List<Vector2>();

		for ( var index = 0; index < loop.Count; index++ )
		{
			var previous = loop[(index - 1 + loop.Count) % loop.Count];
			var current = loop[index];
			var next = loop[(index + 1) % loop.Count];

			if ( MathF.Abs( Cross( previous, next, current ) ) > ArchCarve.Grain )
			{
				kept.Add( current );
			}
		}

		return kept;
	}
}