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

	// The wavefront is found on a CELL GRID, and a grid only tells the truth about edges that lie on it - so it
	// is laid on the footprint's OWN bearing rather than the world's. Read straight, a house turned off the axes
	// came back as a staircase of axis-aligned boxes down its diagonal, each one carrying its own little hip.
	// Coverage is still asked in world terms, because the eaves and the outline are where they really stand.
	static List<List<Vector2>> Wave( IReadOnlyList<IReadOnlyList<Vector2>> loops, List<Eave> eaves, float time ) {
		ArchFootprint.Bearing( loops, out var bearing );

		var pivot = ArchFootprint.Pivot( loops );
		var framed = loops.Select( loop => ArchFootprint.Turned( loop, pivot, -bearing ) ).ToList();
		var points = framed.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 = ArchFootprint.Turned(
					new Vector2( (xs[ix] + xs[ix + 1]) * 0.5f, (ys[iy] + ys[iy + 1]) * 0.5f ), pivot, bearing );

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

		return ArchFootprint.Trace( xs, ys, covered )
			.Select( loop => ArchFootprint.Turned( loop, pivot, bearing ) )
			.ToList();
	}

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

		values.Sort();

		// Near-duplicates COLLAPSE rather than snapping onto a rung. On the world axes the two were the same
		// thing, because every coordinate already stood on one; in a turned footprint's own frame nothing does,
		// so snapping put the two ends of a hip's last band on neighbouring rungs and its apex a third of an
		// inch out - which the engine's own weld then read as a degenerate face and threw the whole hip end away.
		var kept = new List<float>();

		foreach ( var value in values ) {
			if ( kept.Count > 0 && value - kept[^1] <= Grain ) {
				continue;
			}

			kept.Add( value );
		}

		return kept;
	}

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