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

namespace Sunless.Architecture;

// Rotation-minimising frames: a section on a winding, raking curve never spins about its own tangent.
public sealed class ArchCurve
{
	const float DenseStep = 4f;

	const int LongestStraightRun = 8;

	readonly List<ArchCurveNode> nodes;
	readonly bool closed;

	List<ArchFrame> dense;

	ArchCurve( IEnumerable<ArchCurveNode> nodes, bool closed )
	{
		this.nodes = nodes.Select( node => node.Copy() ).ToList();
		this.closed = closed;
	}

	public static ArchCurve Of( IReadOnlyList<ArchCurveNode> nodes, bool closed = false )
	{
		return new ArchCurve( nodes ?? new List<ArchCurveNode>(), closed );
	}

	public static ArchCurve Through( IEnumerable<Vector3> points, bool closed = false )
	{
		return new ArchCurve( points.Select( ArchCurveNode.At ), closed );
	}

	// Corners stay corners: the Auto tangent rounds a rectilinear loop off, and a roof edge has no radius.
	public static ArchCurve Polyline( IEnumerable<Vector3> points, bool closed = false )
	{
		return new ArchCurve(
			points.Select( point => new ArchCurveNode { Position = point, Mode = ArchTangentMode.Linear } ),
			closed );
	}

	public bool IsUsable => nodes.Count >= 2;

	public bool Closed => closed;

	public int NodeCount => nodes.Count;

	public ArchCurveNode Node( int index ) => nodes[Wrapped( index )];

	public IReadOnlyList<ArchFrame> Dense => dense ??= Build();

	public float Length => Dense.Count == 0 ? 0f : Dense[^1].Distance;

	public List<ArchFrame> Walk( float precision, bool simplify = false, float straightThreshold = 1f, int minimumRun = 3 )
	{
		var frames = Stepped( precision );

		if ( !simplify || frames.Count < 3 )
		{
			return frames;
		}

		return Important( frames, straightThreshold, minimumRun ).Select( index => frames[index] ).ToList();
	}

	// Pins station-decided features (dropped kerbs, crossovers) that simplification would otherwise collapse.
	public List<ArchFrame> Walk( float precision, bool simplify, float straightThreshold, int minimumRun, IEnumerable<float> keep )
	{
		var frames = Walk( precision, simplify, straightThreshold, minimumRun );

		if ( keep is null )
		{
			return frames;
		}

		foreach ( var distance in keep )
		{
			Insert( frames, distance );
		}

		return frames;
	}

	static readonly Comparison<ArchFrame> ByDistance = ( a, b ) => a.Distance.CompareTo( b.Distance );

	void Insert( List<ArchFrame> frames, float distance )
	{
		if ( distance < 0f || distance > Length )
		{
			return;
		}

		foreach ( var frame in frames )
		{
			if ( MathF.Abs( frame.Distance - distance ) < 0.5f )
			{
				return;
			}
		}

		if ( !Sample( distance, out var sampled ) )
		{
			return;
		}

		frames.Add( sampled );
		frames.Sort( ByDistance );
	}

	public bool Sample( float distance, out ArchFrame frame )
	{
		var walk = Dense;

		frame = default;

		if ( walk.Count == 0 )
		{
			return false;
		}

		if ( walk.Count == 1 || distance <= 0f )
		{
			frame = walk[0];
			return true;
		}

		if ( distance >= walk[^1].Distance )
		{
			frame = walk[^1];
			return true;
		}

		for ( var index = 0; index < walk.Count - 1; index++ )
		{
			var from = walk[index];
			var to = walk[index + 1];
			var span = to.Distance - from.Distance;

			if ( span < 0.0001f || distance > to.Distance )
			{
				continue;
			}

			frame = Blend( from, to, (distance - from.Distance) / span );

			return true;
		}

		frame = walk[^1];

		return true;
	}

	public bool Nearest( Vector2 point, out ArchFrame frame, out float gap )
	{
		var walk = Dense;

		frame = default;
		gap = float.MaxValue;

		if ( walk.Count == 0 )
		{
			return false;
		}

		for ( var index = 0; index < walk.Count - 1; index++ )
		{
			var from = walk[index];
			var to = walk[index + 1];
			var span = to.Flat - from.Flat;
			var length = span.Length;

			if ( length < 0.01f )
			{
				continue;
			}

			var direction = span / length;
			var along = Math.Clamp( Vector2.Dot( point - from.Flat, direction ), 0f, length );
			var reach = (point - (from.Flat + direction * along)).Length;

			if ( reach >= gap )
			{
				continue;
			}

			gap = reach;
			frame = Blend( from, to, along / length );
		}

		return gap < float.MaxValue;
	}

	// Level services only; anything that rakes reads the frames instead.
	public List<Vector2> Flatten( float precision )
	{
		return Walk( precision, true ).Select( frame => frame.Flat ).ToList();
	}

	public void Invalidate() => dense = null;

	List<ArchFrame> Stepped( float precision )
	{
		var walk = Dense;

		if ( walk.Count < 2 )
		{
			return new List<ArchFrame>( walk );
		}

		var step = MathF.Max( 4f, precision );
		var division = ArchDivide.AtMost( walk[^1].Distance, step );
		var frames = new List<ArchFrame>();

		foreach ( var distance in division.Nodes )
		{
			if ( Sample( distance, out var frame ) )
			{
				frames.Add( frame );
			}
		}

		return frames;
	}

	List<ArchFrame> Build()
	{
		var frames = new List<ArchFrame>();

		if ( nodes.Count < 2 )
		{
			return frames;
		}

		var samples = Positions();

		if ( samples.Count < 2 )
		{
			return frames;
		}

		var reference = Seed( Tangent( samples, 0 ) );
		var travelled = 0f;

		for ( var index = 0; index < samples.Count; index++ )
		{
			var along = Tangent( samples, index );

			if ( index > 0 )
			{
				reference = Transported( samples[index - 1].Position, Tangent( samples, index - 1 ), reference, samples[index].Position, along );
				travelled += (samples[index].Position - samples[index - 1].Position).Length;
			}

			var up = Rotation.FromAxis( along, samples[index].Roll ) * reference;
			var across = Vector3.Cross( along, up ).Normal;

			frames.Add( new ArchFrame
			{
				Position = samples[index].Position,
				Along = along,
				Across = across.IsNearZeroLength ? Vector3.Left : across,
				Up = Vector3.Cross( across, along ).Normal,
				Distance = travelled,
				WidthScale = samples[index].Width
			} );
		}

		return frames;
	}

	readonly record struct Bead( Vector3 Position, float Roll, float Width );

	List<Bead> Positions()
	{
		var samples = new List<Bead>();
		var segments = closed ? nodes.Count : nodes.Count - 1;

		for ( var segment = 0; segment < segments; segment++ )
		{
			var from = nodes[Wrapped( segment )];
			var to = nodes[Wrapped( segment + 1 )];

			Handles( segment, out var lead, out var trail );

			var chord = (to.Position - from.Position).Length + lead.Length + trail.Length;
			var steps = Math.Clamp( (int)MathF.Ceiling( chord / DenseStep ), 1, 512 );

			for ( var step = 0; step < steps; step++ )
			{
				var t = step / (float)steps;

				samples.Add( new Bead(
					Bezier( from.Position, from.Position + lead, to.Position + trail, to.Position, t ),
					MathX.Lerp( from.Roll, to.Roll, t ),
					MathX.Lerp( Scale( from ), Scale( to ), t ) ) );
			}
		}

		var last = nodes[Wrapped( segments )];
		samples.Add( new Bead( last.Position, last.Roll, Scale( last ) ) );

		return samples;
	}

	static float Scale( ArchCurveNode node ) => node.WidthScale <= 0.01f ? 1f : node.WidthScale;

	void Handles( int segment, out Vector3 lead, out Vector3 trail )
	{
		var from = nodes[Wrapped( segment )];
		var to = nodes[Wrapped( segment + 1 )];

		lead = from.Mode switch
		{
			ArchTangentMode.Linear => (to.Position - from.Position) / 3f,
			ArchTangentMode.Auto => Automatic( segment ),
			_ => from.Out
		};

		trail = to.Mode switch
		{
			ArchTangentMode.Linear => (from.Position - to.Position) / 3f,
			ArchTangentMode.Auto => -Automatic( segment + 1 ),
			_ => to.In
		};
	}

	// Catmull-Rom in Bezier clothing: clicks come out one continuous curve, not a polyline.
	Vector3 Automatic( int index )
	{
		var here = nodes[Wrapped( index )].Position;
		var ahead = Reachable( index + 1 ) ? nodes[Wrapped( index + 1 )].Position : here;
		var behind = Reachable( index - 1 ) ? nodes[Wrapped( index - 1 )].Position : here;

		if ( ahead == here )
		{
			return (here - behind) / 3f;
		}

		if ( behind == here )
		{
			return (ahead - here) / 3f;
		}

		return (ahead - behind) / 6f;
	}

	bool Reachable( int index ) => closed || (index >= 0 && index < nodes.Count);

	int Wrapped( int index ) => (index % nodes.Count + nodes.Count) % nodes.Count;

	static Vector3 Bezier( Vector3 a, Vector3 b, Vector3 c, Vector3 d, float t )
	{
		var u = 1f - t;

		return a * (u * u * u) + b * (3f * u * u * t) + c * (3f * u * t * t) + d * (t * t * t);
	}

	static Vector3 Tangent( IReadOnlyList<Bead> samples, int index )
	{
		var ahead = Math.Min( index + 1, samples.Count - 1 );
		var behind = Math.Max( index - 1, 0 );
		var span = samples[ahead].Position - samples[behind].Position;

		return span.IsNearZeroLength ? Vector3.Forward : span.Normal;
	}

	static Vector3 Seed( Vector3 along )
	{
		var reference = MathF.Abs( Vector3.Dot( along, Vector3.Up ) ) > 0.999f ? Vector3.Forward : Vector3.Up;
		var across = Vector3.Cross( along, reference ).Normal;

		return Vector3.Cross( across, along ).Normal;
	}

	// Wang double reflection: minimum rotation onto the next tangent; world-up flips near-vertical.
	static Vector3 Transported( Vector3 from, Vector3 alongFrom, Vector3 normal, Vector3 to, Vector3 alongTo )
	{
		var offset = to - from;
		var half = Vector3.Dot( offset, offset ) * 0.5f;

		if ( half < 0.000001f )
		{
			return normal;
		}

		var reflectedNormal = normal - offset * (Vector3.Dot( offset, normal ) / half);
		var reflectedAlong = alongFrom - offset * (Vector3.Dot( offset, alongFrom ) / half);
		var swing = alongTo - reflectedAlong;
		var swingLength = Vector3.Dot( swing, swing );

		if ( swingLength < 0.000001f )
		{
			return reflectedNormal.Normal;
		}

		return (reflectedNormal - swing * (2f * Vector3.Dot( swing, reflectedNormal ) / swingLength)).Normal;
	}

	static ArchFrame Blend( ArchFrame from, ArchFrame to, float t )
	{
		var along = Vector3.Lerp( from.Along, to.Along, t ).Normal;
		var up = Vector3.Lerp( from.Up, to.Up, t ).Normal;
		var across = Vector3.Cross( along, up ).Normal;

		return new ArchFrame
		{
			Position = Vector3.Lerp( from.Position, to.Position, t ),
			Along = along.IsNearZeroLength ? from.Along : along,
			Across = across.IsNearZeroLength ? from.Across : across,
			Up = across.IsNearZeroLength ? from.Up : Vector3.Cross( across, along ).Normal,
			Distance = MathX.Lerp( from.Distance, to.Distance, t ),
			WidthScale = MathX.Lerp( from.WidthScale, to.WidthScale, t )
		};
	}

	// The threshold anchors on the last frame KEPT, or a long shallow curve collapses end to end and cuts the corner.
	// Collapsed runs are also length-capped: a quarter-mile quad is not something the mapping tool can be handed.
	static List<int> Important( IReadOnlyList<ArchFrame> frames, float threshold, int minimumRun )
	{
		var kept = new List<int> { 0 };
		var straight = new List<int>();
		var anchor = 0;

		for ( var index = 1; index < frames.Count - 1; index++ )
		{
			var drifted = Bend( frames[anchor], frames[index], frames[index + 1] ) >= threshold;
			var stretched = straight.Count + 1 >= LongestStraightRun;

			if ( !drifted && !stretched )
			{
				straight.Add( index );
				continue;
			}

			if ( straight.Count < minimumRun )
			{
				kept.AddRange( straight );
			}

			straight.Clear();
			kept.Add( index );
			anchor = index;
		}

		if ( straight.Count > 0 && straight.Count < minimumRun )
		{
			kept.AddRange( straight );
		}

		kept.Add( frames.Count - 1 );

		return kept.Distinct().OrderBy( index => index ).ToList();
	}

	static float Bend( ArchFrame previous, ArchFrame current, ArchFrame next )
	{
		var into = (current.Position - previous.Position).Normal;
		var outOf = (next.Position - current.Position).Normal;

		if ( into.IsNearZeroLength || outOf.IsNearZeroLength )
		{
			return 0f;
		}

		return MathF.Acos( Math.Clamp( Vector3.Dot( into, outOf ), -1f, 1f ) ).RadianToDegree();
	}
}