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

namespace Sunless.Architecture;

// Stitches a ring (shape inside shape) corner-to-corner; falls back to sweep if it can't tile exactly
static class ArchCarveQuads {
	const int BreakSalt = 71;

	const float LeastBite = ArchGridService.FinestSize * 2f;

	// Ear-clip into triangles, then fuse pairs into the squarest quads available
	public static IEnumerable<List<Vector2>> Split( List<Vector2> loop ) {
		if ( loop.Count <= 4 ) {
			return new[] { loop };
		}

		var wedges = Wedges( loop );

		return wedges.Count == 0 ? new[] { loop } : Fused( wedges );
	}

	static List<List<Vector2>> Wedges( List<Vector2> loop ) {
		var remaining = new List<Vector2>( loop );
		var wedges = new List<List<Vector2>>();

		while ( remaining.Count > 3 ) {
			var clipped = Clipped( remaining );

			if ( clipped < 0 ) {
				return new List<List<Vector2>>();
			}

			var behind = remaining[(clipped - 1 + remaining.Count) % remaining.Count];
			var ahead = remaining[(clipped + 1) % remaining.Count];

			wedges.Add( new List<Vector2> { behind, remaining[clipped], ahead } );
			remaining.RemoveAt( clipped );
		}

		wedges.Add( remaining );

		return wedges;
	}

	static int Clipped( List<Vector2> loop ) {
		for ( var index = 0; index < loop.Count; index++ ) {
			var behind = loop[(index - 1 + loop.Count) % loop.Count];
			var here = loop[index];
			var ahead = loop[(index + 1) % loop.Count];

			if ( Turn( behind, here, ahead ) < ArchCarve.Grain ) {
				continue;
			}

			var wedge = new List<Vector2> { behind, here, ahead };

			if ( loop.Where( corner => !Corner( wedge, corner ) ).Any( corner => ArchFootprint.Contains( wedge, corner ) ) ) {
				continue;
			}

			return index;
		}

		return -1;
	}

	static bool Corner( List<Vector2> wedge, Vector2 corner ) => wedge.Any( held => (held - corner).Length < ArchCarve.Grain );

	static float Turn( Vector2 behind, Vector2 here, Vector2 ahead ) {
		var into = here - behind;
		var away = ahead - here;

		return into.x * away.y - into.y * away.x;
	}

	static List<List<Vector2>> Fused( List<List<Vector2>> wedges ) {
		var taken = new bool[wedges.Count];
		var quads = new List<List<Vector2>>();

		var candidates = new List<(float Cost, int Left, int Right, List<Vector2> Quad)>();

		for ( var left = 0; left < wedges.Count; left++ ) {
			for ( var right = left + 1; right < wedges.Count; right++ ) {
				if ( Fuse( wedges[left], wedges[right] ) is { } quad ) {
					candidates.Add( (Skew( quad ), left, right, quad) );
				}
			}
		}

		foreach ( var (_, left, right, quad) in candidates.OrderBy( candidate => candidate.Cost ) ) {
			if ( taken[left] || taken[right] ) {
				continue;
			}

			taken[left] = true;
			taken[right] = true;

			quads.Add( quad );
		}

		for ( var index = 0; index < wedges.Count; index++ ) {
			if ( !taken[index] ) {
				quads.Add( wedges[index] );
			}
		}

		return quads;
	}

	static List<Vector2> Fuse( List<Vector2> left, List<Vector2> right ) {
		for ( var index = 0; index < left.Count; index++ ) {
			var from = left[index];
			var to = left[(index + 1) % left.Count];

			if ( !Corner( right, from ) || !Corner( right, to ) ) {
				continue;
			}

			var beyond = right.FirstOrDefault( corner => !Corner( new List<Vector2> { from, to }, corner ) );
			var behind = left[(index + 2) % left.Count];
			var quad = new List<Vector2> { behind, from, beyond, to };

			return Convex( quad ) ? quad : null;
		}

		return null;
	}

	static bool Convex( List<Vector2> quad ) {
		for ( var index = 0; index < quad.Count; index++ ) {
			var behind = quad[(index - 1 + quad.Count) % quad.Count];
			var ahead = quad[(index + 1) % quad.Count];

			if ( Turn( behind, quad[index], ahead ) < ArchCarve.Grain ) {
				return false;
			}
		}

		return true;
	}

	static float Skew( List<Vector2> quad ) {
		var skew = 0f;

		for ( var index = 0; index < quad.Count; index++ ) {
			var into = (quad[index] - quad[(index - 1 + quad.Count) % quad.Count]).Normal;
			var away = (quad[(index + 1) % quad.Count] - quad[index]).Normal;

			skew += MathF.Abs( Vector2.Dot( into, away ) );
		}

		return skew;
	}

	public static List<List<Vector2>> Ring( IReadOnlyList<ArchCarveVolume> volumes ) {
		if ( volumes.Count != 2 ) {
			return null;
		}

		var first = Wound( volumes[0].Footprint );
		var second = Wound( volumes[1].Footprint );

		if ( first is null || second is null ) {
			return null;
		}

		var host = Holds( first, second ) ? first : Holds( second, first ) ? second : null;

		if ( host is null ) {
			return null;
		}

		var standing = ReferenceEquals( host, first );
		var hole = Broken( host, standing ? second : first, standing ? volumes[1].Break : volumes[0].Break );
		var faces = Stitched( host, hole );

		return faces is not null && Tiles( faces, host ) ? faces : null;
	}

	static List<Vector2> Wound( IReadOnlyList<Vector2> footprint ) {
		return footprint is { Count: >= 3 } ? ArchFootprint.Wind( footprint.ToList() ) : null;
	}

	static bool Holds( List<Vector2> outer, List<Vector2> inner ) {
		if ( inner.Any( corner => !ArchFootprint.Contains( outer, corner ) ) ) {
			return false;
		}

		for ( var index = 0; index < inner.Count; index++ ) {
			var spans = ArchFootprint.Inside( outer, inner[index], inner[(index + 1) % inner.Count] ).ToList();

			if ( spans.Count != 1 || spans[0].From > 0.001f || spans[0].To < 0.999f ) {
				return false;
			}
		}

		return true;
	}

	// Pulls convex corners inward to simulate disrepair; reflex corners stay put
	static List<Vector2> Broken( List<Vector2> host, List<Vector2> hole, ArchCarveBreak breaking ) {
		if ( !breaking.Breaks ) {
			return hole;
		}

		var bite = Bite( host, hole, breaking.Jitter );

		if ( bite < LeastBite ) {
			return hole;
		}

		var broken = new List<Vector2>();

		for ( var index = 0; index < hole.Count; index++ ) {
			var behind = hole[(index - 1 + hole.Count) % hole.Count];
			var here = hole[index];
			var ahead = hole[(index + 1) % hole.Count];
			var inward = Turn( behind, here, ahead ) < ArchCarve.Grain ? Vector2.Zero : Inward( behind, here, ahead );
			var offset = bite * ArchBarrierShape.Noise( breaking.Seed, index, BreakSalt );

			var bitten = inward.Length > 0.5f && offset >= LeastBite;

			broken.Add( bitten ? ArchGridService.Fine( here + inward * offset ) : here );
		}

		return broken;
	}

	// Clamped to 1/3 of the ring's narrowest gap and 1/4 of the hole's narrowest span
	static float Bite( List<Vector2> host, List<Vector2> hole, float jitter ) {
		ArchFootprint.Bounds( hole, out var min, out var max );

		var gap = MathF.Min( Gap( host, hole ), Gap( hole, host ) );

		return MathF.Min( jitter, MathF.Min( gap / 3f, MathF.Min( max.x - min.x, max.y - min.y ) * 0.25f ) );
	}

	static float Gap( List<Vector2> loop, List<Vector2> against ) {
		var boundary = ArchRunPath.Of( loop, 0f, true );
		var gap = float.MaxValue;

		foreach ( var corner in against ) {
			if ( boundary.Nearest( corner, out _, out var reach ) ) {
				gap = MathF.Min( gap, reach );
			}
		}

		return gap;
	}

	static Vector2 Inward( Vector2 behind, Vector2 here, Vector2 ahead ) {
		var into = (here - behind).Normal;
		var away = (ahead - here).Normal;
		var bisector = new Vector2( -into.y, into.x ) + new Vector2( -away.y, away.x );

		return bisector.Length < 0.0001f ? Vector2.Zero : bisector.Normal;
	}

	static List<List<Vector2>> Stitched( List<Vector2> host, List<Vector2> hole ) {
		var reach = Reach( host, hole );

		if ( Around( reach, host.Count ) != host.Count ) {
			return null;
		}

		var faces = new List<List<Vector2>> { new( hole ) };

		for ( var index = 0; index < hole.Count; index++ ) {
			var next = (index + 1) % hole.Count;
			var corner = reach[index];
			var step = Step( reach[index], reach[next], host.Count );

			if ( step == 0 ) {
				faces.Add( new List<Vector2> { host[corner], hole[next], hole[index] } );

				continue;
			}

			faces.Add( new List<Vector2> { host[corner], host[(corner + 1) % host.Count], hole[next], hole[index] } );

			for ( var extra = 1; extra < step; extra++ ) {
				var at = (corner + extra) % host.Count;

				faces.Add( new List<Vector2> { host[at], host[(at + 1) % host.Count], hole[next] } );
			}
		}

		return faces;
	}

	static int Around( List<int> reach, int corners ) {
		var travelled = 0;

		for ( var index = 0; index < reach.Count; index++ ) {
			travelled += Step( reach[index], reach[(index + 1) % reach.Count], corners );
		}

		return travelled;
	}

	static int Step( int from, int to, int corners ) => (to - from + corners) % corners;

	// Equal corner counts pair by offset (shortest total); unequal pair by nearest angle
	static List<int> Reach( List<Vector2> host, List<Vector2> hole ) {
		if ( host.Count == hole.Count ) {
			return Paired( host, hole );
		}

		var centre = hole.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / hole.Count;

		return hole.Select( corner => Nearest( host, centre, corner ) ).ToList();
	}

	static List<int> Paired( List<Vector2> host, List<Vector2> hole ) {
		var best = 0;
		var shortest = float.MaxValue;

		for ( var offset = 0; offset < host.Count; offset++ ) {
			var total = 0f;

			for ( var index = 0; index < hole.Count; index++ ) {
				total += (host[(index + offset) % host.Count] - hole[index]).Length;
			}

			if ( total < shortest ) {
				shortest = total;
				best = offset;
			}
		}

		return Enumerable.Range( 0, hole.Count ).Select( index => (index + best) % host.Count ).ToList();
	}

	static int Nearest( List<Vector2> host, Vector2 centre, Vector2 corner ) {
		var wanted = MathF.Atan2( corner.y - centre.y, corner.x - centre.x );
		var best = 0;
		var closest = float.MaxValue;

		for ( var index = 0; index < host.Count; index++ ) {
			var angle = MathF.Atan2( host[index].y - centre.y, host[index].x - centre.x ) - wanted;
			var apart = MathF.Abs( MathF.Atan2( MathF.Sin( angle ), MathF.Cos( angle ) ) );

			if ( apart < closest ) {
				closest = apart;
				best = index;
			}
		}

		return best;
	}

	static bool Tiles( List<List<Vector2>> faces, List<Vector2> host ) {
		var wanted = MathF.Abs( ArchFootprint.SignedArea( host ) );
		var covered = 0f;

		foreach ( var face in faces ) {
			var area = ArchFootprint.SignedArea( face );
			var centre = face.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / face.Count;

			if ( area < ArchCarve.Grain || !ArchFootprint.Contains( host, centre ) ) {
				return false;
			}

			if ( face.Count > 3 && !ArchFootprint.IsSimple( face ) ) {
				return false;
			}

			covered += area;
		}

		return MathF.Abs( covered - wanted ) < MathF.Max( 1f, wanted * 0.0001f );
	}
}