namespace AdvancedMappingTools;

public enum WallJoinStyle
{
	Miter,
	Bevel,
	Butt,
	Overlap
}

/// <summary>
/// One stretch of a wall between two distances along its line. Without corners an end is
/// square, with corners it ends on exactly these points of its left and right face.
/// </summary>
public sealed class WallSection
{
	public float From { get; set; }
	public float To { get; set; }
	public Vector3? FromLeft { get; set; }
	public Vector3? FromRight { get; set; }
	public Vector3? ToLeft { get; set; }
	public Vector3? ToRight { get; set; }

	/// <summary>
	/// Points on the faces where another wall ends, so a welded mesh can connect to them.
	/// </summary>
	public List<Vector3> LeftStops { get; set; } = [];
	public List<Vector3> RightStops { get; set; } = [];

	/// <summary>
	/// Points between the two corners of an end, from right to left, where it stops on a curved face.
	/// </summary>
	public List<Vector3> FromEdge { get; set; } = [];
	public List<Vector3> ToEdge { get; set; } = [];
}

/// <summary>
/// One wall as the solver sees it. <see cref="Left"/> and <see cref="Right"/> are how far
/// its faces lie to the left of the line, the right one is negative.
/// </summary>
public sealed record WallInput( IReadOnlyList<Vector3> Path, bool Closed, float Left, float Right, WallJoinStyle Join, float Bottom, float Top );

/// <summary>
/// What the solver found for one wall: how it is cut and which walls it touches.
/// </summary>
public sealed class WallSolution
{
	public List<WallSection> Sections { get; } = [];
	public List<List<Vector3>> Hubs { get; } = [];
	public HashSet<int> Neighbours { get; } = [];
}

/// <summary>
/// Works out how walls meet, from nothing but their lines and thicknesses. Where ends meet at a
/// corner, both are cut on the line through the crossing points of their faces, so
/// nothing overlaps and nothing stays open, at any angle and with any two thicknesses. An end
/// that reaches the side of another wall stops on that face. Of two walls crossing each other
/// one runs through and the other is cut in two. Three walls that meet without a straight
/// pair share a junction piece. Curved walls take part with the direction of their ends.
/// The walls are never merged: this only says where each of them ends.
/// </summary>
public static class WallNetwork
{
	public const float Tolerance = 2.0f;

	const float MaxMitre = 4.0f;
	const float Straight = 0.985f;
	const float EndClearance = 1.0f;

	sealed class Line
	{
		public WallInput Input;
		public PathTrack Track;
		public Vector2[] Center;
		public float[] Along;
		public float Length;
		public readonly List<(float Along, Vector3 Left, Vector3 Right, bool Forward, List<Vector3> Edge)> Cuts = [];
		public readonly List<(float Along, bool Left, Vector3 Point)> Stops = [];
		public (Vector3 Left, Vector3 Right, List<Vector3> Edge)? Start;
		public (Vector3 Left, Vector3 Right, List<Vector3> Edge)? End;

		public Vector2[] Face( float side ) => [.. Enumerable.Range( 0, Track.Count ).Select( i => Flat( Track.Place( i, side ) ) )];

		public Vector2 Tangent( float along )
		{
			var (index, _) = Track.Locate( along );
			return Flat( Track.Frames[index + 1].Position - Track.Frames[index].Position ).Normal;
		}

		public float Height => Track.Frames[0].Position.z;
	}

	/// <summary>
	/// A wall end at a meeting point, seen from there: its direction leads away into the wall.
	/// </summary>
	sealed class Arm
	{
		public int Wall;
		public Vector2 Point;
		public Vector2 Direction;
		public float LeftWidth;
		public float RightWidth;
		public Vector2? Left;
		public Vector2? Right;
		public List<Vector3> Edge = [];
		public bool AtStart;
		public Action<Vector3, Vector3, List<Vector3>> Apply;

		public Vector2 Normal => new( -Direction.y, Direction.x );
		public Vector2 LeftPoint => Point + Normal * LeftWidth;
		public Vector2 RightPoint => Point - Normal * RightWidth;
		public float Width => MathF.Max( LeftWidth + RightWidth, 0.01f );
	}

	static Vector2 Flat( Vector3 v ) => new( v.x, v.y );

	static float Cross( Vector2 a, Vector2 b ) => a.x * b.y - a.y * b.x;

	static Vector2? Meet( Vector2 a, Vector2 da, Vector2 b, Vector2 db )
	{
		var d = Cross( da, db );

		if ( MathF.Abs( d ) < 1e-4f ) return null;

		return a + da * (Cross( b - a, db ) / d);
	}

	public static List<WallSolution> Solve( IReadOnlyList<WallInput> walls )
	{
		var lines = walls.Select( Prepare ).ToList();
		var solutions = walls.Select( _ => new WallSolution() ).ToList();
		var nodes = new List<(Vector2 Point, float Height, List<Arm> Arms)>();

		void AddArm( int wall, bool atStart )
		{
			var line = lines[wall];
			var along = atStart ? 0.0f : line.Length;
			var point = atStart ? line.Center[0] : line.Center[^1];
			var height = line.Height;
			var direction = atStart ? Flat( line.Center[1] - line.Center[0] ).Normal : Flat( line.Center[^2] - line.Center[^1] ).Normal;

			var arm = new Arm
			{
				Wall = wall,
				Point = point,
				Direction = direction,
				LeftWidth = atStart ? line.Input.Left : -line.Input.Right,
				RightWidth = atStart ? -line.Input.Right : line.Input.Left,
				AtStart = atStart,
				Apply = ( left, right, edge ) =>
				{
					if ( atStart ) line.Start = (left, right, edge);
					else line.End = (right, left, [.. edge.AsEnumerable().Reverse()]);
				}
			};

			foreach ( var node in nodes )
			{
				if ( node.Point.Distance( point ) > Tolerance ) continue;
				if ( !Overlaps( line, lines[node.Arms[0].Wall] ) ) continue;

				node.Arms.Add( arm );
				return;
			}

			nodes.Add( (point, height, [arm]) );
		}

		for ( var w = 0; w < lines.Count; w++ )
		{
			if ( lines[w].Input.Closed ) continue;

			AddArm( w, true );
			AddArm( w, false );
		}

		foreach ( var (point, _, arms) in nodes )
		{
			if ( arms.Count == 1 )
			{
				ButtOntoWall( lines, solutions, arms[0], point );
				continue;
			}

			foreach ( var arm in arms )
				foreach ( var other in arms.Where( x => x != arm ) )
					solutions[arm.Wall].Neighbours.Add( other.Wall );

			var style = arms.Select( x => lines[x.Wall].Input.Join ).Min();

			if ( arms.Count == 2 ) SolveCorner( arms[0], arms[1], style, lines, solutions );
			else SolveJunction( arms, lines, solutions );
		}

		FindCrossings( lines, solutions );

		for ( var w = 0; w < lines.Count; w++ )
			Assemble( lines[w], solutions[w] );

		return solutions;
	}

	static Line Prepare( WallInput input )
	{
		var track = PathTrack.Along( input.Path, input.Closed );
		var center = Enumerable.Range( 0, track.Count ).Select( i => Flat( track.Frames[i].Position ) ).ToArray();

		return new Line
		{
			Input = input,
			Track = track,
			Center = center,
			Along = [.. track.Frames.Select( x => x.Distance )],
			Length = track.Length
		};
	}

	static bool Overlaps( Line a, Line b ) => a.Input.Bottom < b.Input.Top - 0.01f && b.Input.Bottom < a.Input.Top - 0.01f;

	static Vector3 Lift( Vector2 p ) => new( p.x, p.y, 0.0f );

	static void Finish( Arm arm )
	{
		if ( arm.Left is Vector2 left && arm.Right is Vector2 right )
			arm.Apply( Lift( left ), Lift( right ), arm.Edge );
	}

	/// <summary>
	/// Two ends meeting. Going counter clockwise from the first wall to the second, the left
	/// face of the first looks at the right face of the second.
	/// </summary>
	static void SolveCorner( Arm a, Arm b, WallJoinStyle style, List<Line> lines, List<WallSolution> solutions )
	{
		if ( style == WallJoinStyle.Overlap ) return;

		// One straight line: the ends meet on a square cut.
		if ( a.Direction.Dot( b.Direction ) < -Straight ) return;

		var turn = Cross( a.Direction, b.Direction );

		if ( MathF.Abs( turn ) < 0.02f ) return;

		// The sector inside the turn lies left of whichever wall comes first going counter clockwise.
		if ( turn < 0.0f ) (a, b) = (b, a);

		if ( style == WallJoinStyle.Butt )
		{
			SolveButt( a, b, lines );
			return;
		}

		var inner = Meet( a.LeftPoint, a.Direction, b.RightPoint, b.Direction );
		var outer = Meet( a.RightPoint, a.Direction, b.LeftPoint, b.Direction );

		if ( inner is not Vector2 c1 || outer is not Vector2 c2 ) return;

		a.Left = c1;
		b.Right = c1;

		var limit = MaxMitre * MathF.Max( a.Width, b.Width ) * 0.5f;

		if ( style == WallJoinStyle.Miter && c2.Distance( a.Point ) <= limit )
		{
			a.Right = c2;
			b.Left = c2;
		}
		else
		{
			// A bevel: both outer faces stop at the meeting point and a piece closes the gap.
			a.Right = a.RightPoint;
			b.Left = b.LeftPoint;

			solutions[a.Wall].Hubs.Add( [Lift( c1 ), Lift( a.RightPoint ), Lift( b.LeftPoint )] );
		}

		Finish( a );
		Finish( b );
	}

	/// <summary>
	/// The older wall runs on to the outside of the corner, the newer one stops on its face.
	/// </summary>
	static void SolveButt( Arm a, Arm b, List<Line> lines )
	{
		var (through, stopping) = a.Wall < b.Wall ? (a, b) : (b, a);

		var onLeft = stopping.Direction.Dot( through.Normal ) > 0.0f;
		var nearSide = onLeft ? through.LeftPoint : through.RightPoint;
		var farPoint = through.Direction.Dot( stopping.Normal ) < 0.0f ? stopping.LeftPoint : stopping.RightPoint;

		stopping.Left = Meet( stopping.LeftPoint, stopping.Direction, nearSide, through.Direction );
		stopping.Right = Meet( stopping.RightPoint, stopping.Direction, nearSide, through.Direction );
		through.Left = Meet( through.LeftPoint, through.Direction, farPoint, stopping.Direction );
		through.Right = Meet( through.RightPoint, through.Direction, farPoint, stopping.Direction );

		Finish( through );
		Finish( stopping );

		// The end of the other wall lands on this face, so the face gets corners there.
		var line = lines[through.Wall];
		var along = through.AtStart ? 0.0f : line.Length;
		var wallLeft = onLeft == through.AtStart;

		line.Stops.Add( (along, wallLeft, Lift( stopping.Left.Value )) );
		line.Stops.Add( (along, wallLeft, Lift( stopping.Right.Value )) );
	}

	/// <summary>
	/// Three or more ends. Going around the point, neighbours meet where their faces cross. Two
	/// ends in one line have no such point on their shared side: they stop square. What is left
	/// in the middle is a piece of its own, with a corner for each end around it.
	/// </summary>
	static void SolveJunction( List<Arm> arms, List<Line> lines, List<WallSolution> solutions )
	{
		var sorted = arms.OrderBy( x => MathF.Atan2( x.Direction.y, x.Direction.x ) ).ToList();

		for ( var i = 0; i < sorted.Count; i++ )
		{
			var a = sorted[i];
			var b = sorted[(i + 1) % sorted.Count];

			if ( Cross( a.Direction, b.Direction ) <= 0.02f ) continue;

			if ( Meet( a.LeftPoint, a.Direction, b.RightPoint, b.Direction ) is Vector2 c )
			{
				a.Left = c;
				b.Right = c;
			}
		}

		foreach ( var arm in sorted )
		{
			arm.Left ??= arm.Right is Vector2 right ? right + arm.Normal * arm.Width : arm.LeftPoint;
			arm.Right ??= arm.Left.Value - arm.Normal * arm.Width;

			Finish( arm );
		}

		var corners = new List<Vector3>();

		void Corner( Vector2 point )
		{
			var lifted = Lift( point );

			if ( corners.Count == 0 || corners[^1].Distance( lifted ) > 0.01f )
				corners.Add( lifted );
		}

		foreach ( var arm in sorted )
		{
			Corner( arm.Right.Value );
			Corner( arm.Left.Value );
		}

		if ( corners.Count > 1 && corners[^1].Distance( corners[0] ) < 0.01f )
			corners.RemoveAt( corners.Count - 1 );

		if ( corners.Count >= 3 ) solutions[sorted[0].Wall].Hubs.Add( corners );
	}

	/// <summary>
	/// An end on its own may reach the side of another wall.
	/// </summary>
	static void ButtOntoWall( List<Line> lines, List<WallSolution> solutions, Arm arm, Vector2 point )
	{
		var best = -1;
		var bestAlong = 0.0f;
		var bestDistance = float.MaxValue;

		for ( var w = 0; w < lines.Count; w++ )
		{
			if ( w == arm.Wall || !Overlaps( lines[w], lines[arm.Wall] ) ) continue;

			var line = lines[w];
			var (distance, along) = Closest( line, point );
			var reach = MathF.Max( line.Input.Left, -line.Input.Right ) + Tolerance;

			if ( distance > reach || distance >= bestDistance ) continue;
			if ( !line.Input.Closed && (along < EndClearance || along > line.Length - EndClearance) ) continue;

			best = w;
			bestAlong = along;
			bestDistance = distance;
		}

		if ( best < 0 ) return;

		StopOnFace( lines[arm.Wall], lines[best], arm, bestAlong );

		solutions[arm.Wall].Neighbours.Add( best );
		solutions[best].Neighbours.Add( arm.Wall );
	}

	static void StopOnFace( Line wall, Line through, Arm arm, float along )
	{
		var tangent = through.Tangent( along );
		var left = arm.Direction.Dot( new Vector2( -tangent.y, tangent.x ) ) > 0.0f;
		var face = through.Face( left ? through.Input.Left : through.Input.Right );

		arm.Left = Hit( face, through.Input.Closed, arm.LeftPoint, arm.Direction ) ?? arm.LeftPoint;
		arm.Right = Hit( face, through.Input.Closed, arm.RightPoint, arm.Direction ) ?? arm.RightPoint;
		arm.Edge = Between( face, arm.Right.Value, arm.Left.Value );

		Finish( arm );

		through.Stops.Add( (along, left, Lift( arm.Left.Value )) );
		through.Stops.Add( (along, left, Lift( arm.Right.Value )) );
	}

	/// <summary>
	/// The corners of a chain between two points on it, in the order from the first to the second.
	/// On a curved face an end has to follow them, a straight cut would reach into the wall.
	/// </summary>
	static List<Vector3> Between( Vector2[] chain, Vector2 from, Vector2 to )
	{
		float Place( Vector2 point )
		{
			var best = (Distance: float.MaxValue, At: 0.0f);

			for ( var i = 0; i + 1 < chain.Length; i++ )
			{
				var d = chain[i + 1] - chain[i];
				var t = d.LengthSquared > 0.0f ? Math.Clamp( (point - chain[i]).Dot( d ) / d.LengthSquared, 0.0f, 1.0f ) : 0.0f;
				var distance = (chain[i] + d * t).Distance( point );

				if ( distance < best.Distance ) best = (distance, i + t);
			}

			return best.At;
		}

		var a = Place( from );
		var b = Place( to );
		var points = new List<Vector3>();

		for ( var i = (int)MathF.Ceiling( MathF.Min( a, b ) + 0.001f ); i <= (int)MathF.Floor( MathF.Max( a, b ) - 0.001f ); i++ )
			points.Add( Lift( chain[i] ) );

		if ( a > b ) points.Reverse();

		return points;
	}

	/// <summary>
	/// Where a line through a point meets a chain of segments, the crossing closest to the point.
	/// </summary>
	static Vector2? Hit( Vector2[] chain, bool closed, Vector2 point, Vector2 direction )
	{
		var best = default( Vector2? );
		var bestDistance = float.MaxValue;

		for ( var i = 0; i + 1 < chain.Length; i++ )
		{
			var a = chain[i];
			var b = chain[i + 1];
			var along = b - a;
			var d = Cross( direction, along );

			if ( MathF.Abs( d ) < 1e-5f ) continue;

			var t = Cross( a - point, along ) / d;
			var u = Cross( a - point, direction ) / d;

			// The ends of the chain reach a little further, a wall may stop right at the corner of another.
			if ( u < -0.05f || u > 1.05f ) continue;

			var distance = MathF.Abs( t );

			if ( distance >= bestDistance ) continue;

			best = point + direction * t;
			bestDistance = distance;
		}

		return best;
	}

	static (float Distance, float Along) Closest( Line line, Vector2 point )
	{
		var best = (Distance: float.MaxValue, Along: 0.0f);

		for ( var i = 0; i + 1 < line.Center.Length; i++ )
		{
			var a = line.Center[i];
			var b = line.Center[i + 1];
			var d = b - a;
			var t = d.LengthSquared > 0.0f ? Math.Clamp( (point - a).Dot( d ) / d.LengthSquared, 0.0f, 1.0f ) : 0.0f;
			var on = a + d * t;
			var distance = on.Distance( point );

			if ( distance < best.Distance )
				best = (distance, line.Along[i] + (line.Along[i + 1] - line.Along[i]) * t);
		}

		return best;
	}

	/// <summary>
	/// Two walls crossing in their middle: the thicker runs through, the other is cut around it.
	/// </summary>
	static void FindCrossings( List<Line> lines, List<WallSolution> solutions )
	{
		for ( var a = 0; a < lines.Count; a++ )
		{
			for ( var b = a + 1; b < lines.Count; b++ )
			{
				if ( !Overlaps( lines[a], lines[b] ) ) continue;

				foreach ( var (alongA, alongB, point) in Crossings( lines[a], lines[b] ) )
				{
					var aThick = lines[a].Input.Left - lines[a].Input.Right;
					var bThick = lines[b].Input.Left - lines[b].Input.Right;
					var cutB = aThick > bThick - 0.01f || lines[b].Input.Closed;

					if ( cutB && lines[b].Input.Closed ) continue;

					var (through, cut, atThrough, atCut, cutIndex) = cutB ? (lines[a], lines[b], alongA, alongB, b) : (lines[b], lines[a], alongB, alongA, a);

					CutAround( through, cut, cutIndex, atThrough, atCut, point );

					solutions[a].Neighbours.Add( b );
					solutions[b].Neighbours.Add( a );
				}
			}
		}
	}

	static IEnumerable<(float AlongA, float AlongB, Vector2 Point)> Crossings( Line a, Line b )
	{
		for ( var i = 0; i + 1 < a.Center.Length; i++ )
		{
			for ( var j = 0; j + 1 < b.Center.Length; j++ )
			{
				var p = a.Center[i];
				var r = a.Center[i + 1] - p;
				var q = b.Center[j];
				var s = b.Center[j + 1] - q;
				var d = Cross( r, s );

				if ( MathF.Abs( d ) < 1e-5f ) continue;

				var t = Cross( q - p, s ) / d;
				var u = Cross( q - p, r ) / d;

				if ( t < 0.0f || t > 1.0f || u < 0.0f || u > 1.0f ) continue;

				var alongA = a.Along[i] + (a.Along[i + 1] - a.Along[i]) * t;
				var alongB = b.Along[j] + (b.Along[j + 1] - b.Along[j]) * u;

				// Ends are handled as ends.
				var endA = !a.Input.Closed && (alongA < Tolerance + a.Input.Left || alongA > a.Length - Tolerance - a.Input.Left);
				var endB = !b.Input.Closed && (alongB < Tolerance + b.Input.Left || alongB > b.Length - Tolerance - b.Input.Left);

				if ( endA || endB ) continue;

				yield return (alongA, alongB, p + r * t);
			}
		}
	}

	static void CutAround( Line through, Line cut, int cutIndex, float atThrough, float atCut, Vector2 point )
	{
		var tangent = cut.Tangent( atCut );

		var ahead = new Arm { Wall = cutIndex, Point = point, Direction = tangent, LeftWidth = cut.Input.Left, RightWidth = -cut.Input.Right };
		var behind = new Arm { Wall = cutIndex, Point = point, Direction = -tangent, LeftWidth = -cut.Input.Right, RightWidth = cut.Input.Left };

		ahead.Apply = ( left, right, edge ) => cut.Cuts.Add( (atCut, left, right, true, edge) );
		behind.Apply = ( left, right, edge ) => cut.Cuts.Add( (atCut, right, left, false, [.. edge.AsEnumerable().Reverse()]) );

		StopOnFace( cut, through, ahead, atThrough );
		StopOnFace( cut, through, behind, atThrough );
	}

	/// <summary>
	/// How far along a wall's line a point on one of its faces lies.
	/// </summary>
	static float AlongOf( Line line, Vector3 point ) => Closest( line, Flat( point ) ).Along;

	static void Assemble( Line line, WallSolution solution )
	{
		var section = new WallSection { From = 0.0f, To = line.Length };

		if ( line.Start is (Vector3 startLeft, Vector3 startRight, var startEdge) )
		{
			section.FromLeft = startLeft;
			section.FromRight = startRight;
			section.FromEdge = startEdge;
			section.From = MathF.Max( AlongOf( line, startLeft ), AlongOf( line, startRight ) );
		}

		var ends = line.End;
		var cuts = line.Cuts.OrderBy( x => x.Along ).ThenBy( x => x.Forward ).ToList();

		for ( var i = 0; i + 1 < cuts.Count; i += 2 )
		{
			var stop = cuts[i];
			var start = cuts[i + 1];

			section.To = MathF.Min( AlongOf( line, stop.Left ), AlongOf( line, stop.Right ) );
			section.ToLeft = stop.Left;
			section.ToRight = stop.Right;
			section.ToEdge = stop.Edge;
			solution.Sections.Add( section );

			section = new WallSection
			{
				From = MathF.Max( AlongOf( line, start.Left ), AlongOf( line, start.Right ) ),
				To = line.Length,
				FromLeft = start.Left,
				FromRight = start.Right,
				FromEdge = start.Edge
			};
		}

		if ( ends is (Vector3 endLeft, Vector3 endRight, var endEdge) )
		{
			section.ToLeft = endLeft;
			section.ToRight = endRight;
			section.ToEdge = endEdge;
			section.To = MathF.Min( AlongOf( line, endLeft ), AlongOf( line, endRight ) );
		}

		solution.Sections.Add( section );

		foreach ( var (along, left, point) in line.Stops )
		{
			var owner = solution.Sections.FirstOrDefault( x => along >= x.From - 0.01f && along <= x.To + 0.01f );

			if ( owner is null ) continue;

			if ( left ) owner.LeftStops.Add( point );
			else owner.RightStops.Add( point );
		}
	}
}