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

namespace Sunless.Architecture;

// A uniform-pitch hip roof is its footprint's straight skeleton - the L-infinity distance to the boundary,
// so a reflex corner throws a straight 45° valley. An edge dying into a taller wall is open: no face, cut off flush.
public sealed class ArchRoofShape
{
	public List<List<Vector3>> Faces { get; } = new();
	public List<(Vector3 From, Vector3 To)> Creases { get; } = new();
	public List<(Vector3 From, Vector3 To)> Flashing { get; } = new();

	public void Add( Vector3 from, Vector3 to )
	{
		if ( (to - from).Length > 1f )
		{
			Creases.Add( (from, to) );
		}
	}
}

public static class ArchRoofSkeleton
{
	const float Grain = 0.02f;

	readonly struct Eave
	{
		public Vector2 Origin { get; init; }
		public Vector2 Direction { get; init; }
		public Vector2 Normal { get; init; }
		public float Length { get; init; }
		public float Offset { get; init; }
	}

	// The nominal arrival over any point, public because the plane, the elevation and every seat query must
	// measure the deck the way the skeleton builds it.
	public static float Arrival( IReadOnlyList<IReadOnlyList<Vector2>> loops, Vector2 point )
	{
		var eaves = new List<Eave>();
		var walls = new List<Eave>();

		Collect( loops, null, eaves, walls );

		return eaves.Count == 0 ? 0f : Arrival( eaves, point );
	}

	// How deep the wavefront ever reaches - the ridge line's own arrival, so a cut asking for the top of a hip
	// gets the built peak rather than the bounding box's. An event is only a CANDIDATE, offered by any facing
	// pair however far apart, so the answer is the largest one the wave still covers.
	public static float Depth( IReadOnlyList<IReadOnlyList<Vector2>> loops )
	{
		var eaves = new List<Eave>();
		var walls = new List<Eave>();

		Collect( loops, null, eaves, walls );

		if ( eaves.Count == 0 )
		{
			return 0f;
		}

		var events = Events( eaves, walls );

		for ( var index = events.Count - 1; index > 0; index-- )
		{
			if ( Wave( loops, eaves, (events[index - 1] + events[index]) * 0.5f ).Count > 0 )
			{
				return events[index];
			}
		}

		return 0f;
	}

	public static ArchRoofShape Shape( IReadOnlyList<IReadOnlyList<Vector2>> loops, Func<Vector2, Vector2, bool> open, float baseHeight, float slope )
	{
		var shape = new ArchRoofShape();
		var eaves = new List<Eave>();
		var walls = new List<Eave>();

		Collect( loops, open, eaves, walls );

		if ( eaves.Count == 0 )
		{
			return shape;
		}

		// An abutted joint gets the same capping a ridge does - flashing up the wall.
		foreach ( var wall in walls )
		{
			var from = wall.Origin;
			var to = wall.Origin + wall.Direction * wall.Length;

			shape.Flashing.Add( (
				new Vector3( from.x, from.y, baseHeight + slope * Arrival( eaves, from ) ),
				new Vector3( to.x, to.y, baseHeight + slope * Arrival( eaves, to ) )) );
		}

		var events = Events( eaves, walls );

		// Every event comes from a facing pair, so an outline with no two anti-parallel edges - a triangle, an
		// ellipse - offers none and would silently build nothing at all.
		if ( events.Count <= 1 )
		{
			Log.Warning( $"Architecture: a hip roof over {eaves.Count} eaves found no facing pair, so no deck was built - square the outline or use another style." );

			return shape;
		}

		for ( var index = 0; index + 1 < events.Count; index++ )
		{
			var from = events[index];
			var to = events[index + 1];

			if ( to - from < Grain )
			{
				continue;
			}

			var sample = (from + to) * 0.5f;
			var wave = Wave( loops, eaves, sample );

			if ( wave.Count == 0 )
			{
				break;
			}

			foreach ( var loop in wave )
			{
				Band( shape, loop, walls, sample, from, to, baseHeight, slope );
			}
		}

		return shape;
	}

	static void Collect( IReadOnlyList<IReadOnlyList<Vector2>> loops, Func<Vector2, Vector2, bool> open, List<Eave> eaves, List<Eave> walls )
	{
		foreach ( var loop in loops )
		{
			if ( loop is not { Count: >= 3 } )
			{
				continue;
			}

			for ( var index = 0; index < loop.Count; index++ )
			{
				var origin = loop[index];
				var span = loop[(index + 1) % loop.Count] - origin;
				var length = span.Length;

				if ( length < Grain )
				{
					continue;
				}

				var direction = span / length;
				var normal = new Vector2( -direction.y, direction.x );

				var eave = new Eave
				{
					Origin = origin,
					Direction = direction,
					Normal = normal,
					Length = length,
					Offset = Vector2.Dot( normal, origin )
				};

				var target = open is not null && open( origin + direction * (length * 0.5f), -normal ) ? walls : eaves;

				target.Add( eave );
			}
		}
	}

	// Arrival = L-infinity distance; an eave behind the point belongs to another wing and is dropped.
	static float Arrival( List<Eave> eaves, Vector2 point )
	{
		var best = float.MaxValue;

		foreach ( var eave in eaves )
		{
			var perpendicular = Vector2.Dot( eave.Normal, point ) - eave.Offset;

			if ( perpendicular < -Grain )
			{
				continue;
			}

			var along = Vector2.Dot( point - eave.Origin, eave.Direction );
			var lateral = MathF.Max( 0f, MathF.Max( -along, along - eave.Length ) );

			best = MathF.Min( best, MathF.Max( perpendicular, lateral ) );
		}

		return best == float.MaxValue ? 0f : best;
	}

	// Facing eaves close at half their gap; against a wall, at the full gap - all topology events happen there.
	static List<float> Events( List<Eave> eaves, List<Eave> walls )
	{
		var times = new List<float> { 0f };

		void Consider( float closes )
		{
			if ( closes > Grain && !times.Any( time => MathF.Abs( time - closes ) < Grain ) )
			{
				times.Add( closes );
			}
		}

		for ( var first = 0; first < eaves.Count; first++ )
		{
			for ( var second = first + 1; second < eaves.Count; second++ )
			{
				if ( Vector2.Dot( eaves[first].Normal, eaves[second].Normal ) < -0.99f )
				{
					Consider( -(eaves[first].Offset + eaves[second].Offset) * 0.5f );
				}
			}

			foreach ( var wall in walls )
			{
				if ( Vector2.Dot( eaves[first].Normal, wall.Normal ) < -0.99f )
				{
					Consider( -wall.Offset - eaves[first].Offset );
				}
			}
		}

		times.Sort();

		return times;
	}

	static List<List<Vector2>> Wave( IReadOnlyList<IReadOnlyList<Vector2>> loops, List<Eave> eaves, float time )
	{
		var points = loops.SelectMany( loop => loop ).ToList();
		var xs = Axis( points.Select( point => point.x ), time );
		var ys = Axis( points.Select( point => point.y ), time );
		var columns = xs.Count - 1;
		var covered = new bool[columns * (ys.Count - 1)];

		for ( var ix = 0; ix < columns; ix++ )
		{
			for ( var iy = 0; iy + 1 < ys.Count; iy++ )
			{
				var centre = new Vector2( (xs[ix] + xs[ix + 1]) * 0.5f, (ys[iy] + ys[iy + 1]) * 0.5f );

				covered[iy * columns + ix] = Arrival( eaves, centre ) >= time + Grain
					&& ArchFootprint.Encloses( loops, centre );
			}
		}

		return ArchFootprint.Trace( xs, ys, covered );
	}

	static List<float> Axis( IEnumerable<float> coordinates, float time )
	{
		var values = new List<float>();

		foreach ( var coordinate in coordinates )
		{
			values.Add( coordinate - time );
			values.Add( coordinate );
			values.Add( coordinate + time );
		}

		return values.Select( ArchGridService.Fine ).Distinct().OrderBy( value => value ).ToList();
	}

	// Vertices ride edge bisectors so the band sweeps analytically; a collapse that drops out is a hip.
	static void Band( ArchRoofShape shape, List<Vector2> loop, List<Eave> walls, float sample, float from, float to, float baseHeight, float slope )
	{
		if ( loop.Count < 3 )
		{
			return;
		}

		var speed = new float[loop.Count];
		var velocity = new Vector2[loop.Count];

		for ( var index = 0; index < loop.Count; index++ )
		{
			speed[index] = Standing( walls, loop[index], loop[(index + 1) % loop.Count] ) ? 0f : 1f;
		}

		for ( var index = 0; index < loop.Count; index++ )
		{
			var behind = (index - 1 + loop.Count) % loop.Count;

			velocity[index] = Bisector(
				Inward( loop[index] - loop[behind] ), speed[behind],
				Inward( loop[(index + 1) % loop.Count] - loop[index] ), speed[index] );
		}

		for ( var index = 0; index < loop.Count; index++ )
		{
			if ( speed[index] <= 0f )
			{
				continue;
			}

			var next = (index + 1) % loop.Count;

			var face = new List<Vector3>
			{
				At( loop[index], velocity[index], sample, from, baseHeight, slope ),
				At( loop[next], velocity[next], sample, from, baseHeight, slope ),
				At( loop[next], velocity[next], sample, to, baseHeight, slope ),
				At( loop[index], velocity[index], sample, to, baseHeight, slope )
			};

			Emit( shape.Faces, face );
		}

		Creases( shape, loop, speed, velocity, sample, from, to, baseHeight, slope );
	}

	// Convex vertex = hip; reflex = valley (flashed flat, not capped); lines meeting at band end = ridge.
	static void Creases( ArchRoofShape shape, List<Vector2> loop, float[] speed, Vector2[] velocity, float sample, float from, float to, float baseHeight, float slope )
	{
		var reach = to - sample;

		for ( var index = 0; index < loop.Count; index++ )
		{
			var behind = (index - 1 + loop.Count) % loop.Count;

			if ( speed[behind] <= 0f || speed[index] <= 0f || !Convex( loop, index ) )
			{
				continue;
			}

			shape.Add(
				At( loop[index], velocity[index], sample, from, baseHeight, slope ),
				At( loop[index], velocity[index], sample, to, baseHeight, slope ) );
		}

		for ( var index = 0; index < loop.Count; index++ )
		{
			var next = (index + 1) % loop.Count;

			if ( speed[index] <= 0f || !Closes( loop, speed, index, reach ) )
			{
				continue;
			}

			shape.Add(
				At( loop[index], velocity[index], sample, to, baseHeight, slope ),
				At( loop[next], velocity[next], sample, to, baseHeight, slope ) );
		}
	}

	static bool Closes( List<Vector2> loop, float[] speed, int index, float reach )
	{
		var normal = Inward( loop[(index + 1) % loop.Count] - loop[index] );
		var offset = Vector2.Dot( normal, loop[index] );

		for ( var other = index + 1; other < loop.Count; other++ )
		{
			if ( speed[other] <= 0f )
			{
				continue;
			}

			var facing = Inward( loop[(other + 1) % loop.Count] - loop[other] );

			if ( Vector2.Dot( normal, facing ) > -0.99f )
			{
				continue;
			}

			if ( MathF.Abs( offset + Vector2.Dot( facing, loop[other] ) + reach * 2f ) < Grain * 4f )
			{
				return true;
			}
		}

		return false;
	}

	static bool Convex( List<Vector2> loop, int index )
	{
		var into = loop[index] - loop[(index - 1 + loop.Count) % loop.Count];
		var outOf = loop[(index + 1) % loop.Count] - loop[index];

		return into.x * outOf.y - into.y * outOf.x > 0f;
	}

	// An edge on an abutment's line IS that wall - it stands still while the loop marches past.
	static bool Standing( List<Eave> walls, Vector2 from, Vector2 to )
	{
		if ( walls.Count == 0 )
		{
			return false;
		}

		var normal = Inward( to - from );
		var offset = Vector2.Dot( normal, from );

		return walls.Any( wall => Vector2.Dot( wall.Normal, normal ) > 0.99f && MathF.Abs( wall.Offset - offset ) < Grain );
	}

	static void Emit( List<List<Vector3>> faces, List<Vector3> face )
	{
		var kept = new List<Vector3>();

		foreach ( var point in face )
		{
			if ( kept.Count > 0 && (kept[^1] - point).Length < Grain )
			{
				continue;
			}

			kept.Add( point );
		}

		if ( kept.Count > 2 && (kept[0] - kept[^1]).Length < Grain )
		{
			kept.RemoveAt( kept.Count - 1 );
		}

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

	static Vector3 At( Vector2 origin, Vector2 velocity, float sample, float time, float baseHeight, float slope )
	{
		var point = origin + velocity * (time - sample);

		return new Vector3( point.x, point.y, baseHeight + slope * time );
	}

	static Vector2 Inward( Vector2 span )
	{
		var direction = span.Normal;

		return new Vector2( -direction.y, direction.x );
	}

	// Keeps pace with both edges: normal . velocity = that edge's speed (1 eave, 0 wall).
	static Vector2 Bisector( Vector2 first, float firstSpeed, Vector2 second, float secondSpeed )
	{
		var determinant = first.x * second.y - first.y * second.x;

		if ( MathF.Abs( determinant ) < 0.01f )
		{
			return first * firstSpeed;
		}

		return new Vector2(
			(firstSpeed * second.y - secondSpeed * first.y) / determinant,
			(secondSpeed * first.x - firstSpeed * second.x) / determinant );
	}
}