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();

	// Weld table — all manufactured points snap to the grid to prevent slivers from rounding
	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;
	}

	// Ring produces true quads; sweep produces rectangles with mid-side vertices
	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] );
			}
		}
	}

	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,
			Centre = centre / loop.Count,
			Min = min,
			Max = max
		};
	}

	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
				} );
			}
		}

		// Check neighbouring buckets — rounding can split collinear edges across boundaries
		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 ) );
	}

	// Bucket key only proposes a shared line — verify collinearity precisely
	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;
	}

	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;

		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 );
	}

	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;
	}

	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;
	}

	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;
	}
}