namespace AdvancedMappingTools;
/// <summary>
/// The kind of quarter the World Builder lays out. It decides the street grid, the plot sizes and
/// what stands on the plots.
/// </summary>
public enum DistrictStyle
{
	[Title( "Residential" ), Icon( "home" )] Residential,
	[Title( "Industrial" ), Icon( "factory" )] Industrial,
	[Title( "Old Town" ), Icon( "castle" )] OldTown,
	[Title( "Coastal Town" ), Icon( "sailing" )] Coastal
}

/// <summary>
/// What a plot is meant for. The World Builder later places the matching building tool on it.
/// </summary>
public enum PlotUse
{
	House,
	Apartment,
	/// <summary>No longer placed; layouts saved with it build a house there.</summary>
	Shop,
	Warehouse,
	Green,
	Parking
}

public sealed record DistrictStreet( Vector2 A, Vector2 B, float Width );

public sealed record DistrictJunction( Vector2 At, IReadOnlyList<Vector2> Arms );

public sealed record DistrictBlock( IReadOnlyList<Vector2> Ring );

/// <summary>
/// One plot. <see cref="Front"/> is the middle of its street edge and <see cref="Facing"/> points from
/// the plot to that street, so a building can turn its door there.
/// </summary>
public sealed record DistrictPlot( IReadOnlyList<Vector2> Ring, Vector2 Front, Vector2 Facing, float Frontage, float Depth, PlotUse Use, int Block );

public sealed class DistrictPlan
{
	public List<DistrictStreet> Streets { get; } = [];
	public List<DistrictJunction> Junctions { get; } = [];
	public List<DistrictBlock> Blocks { get; } = [];
	public List<DistrictPlot> Plots { get; } = [];
}

/// <summary>
/// Values that shape the layout. <see cref="DistrictLayout.Defaults"/> gives what each style uses.
/// </summary>
public sealed class DistrictLayoutSettings
{
	public DistrictStyle Style { get; set; } = DistrictStyle.Residential;
	public float BlockSize { get; set; } = 2048.0f;

	public float BlockAspect { get; set; } = 1;
	public float StreetWidth { get; set; } = 384.0f;
	public float PlotWidth { get; set; } = 448.0f;
	public float PlotDepth { get; set; } = 512.0f;
	public float Irregularity { get; set; } = 0.0f;
	public float Angle { get; set; } = 0.0f;
	public int Seed { get; set; } = 1;
}

/// <summary>
/// Lays out a quarter inside a drawn outline: streets on a grid that may be bent, blocks between
/// them and plots along the street sides of each block. Pure math without a scene, so it is tested
/// on its own and gives the same result for the same seed.
/// </summary>
public static class DistrictLayout
{
	public static DistrictLayoutSettings Defaults( DistrictStyle style ) => style switch
	{
		DistrictStyle.Industrial => new() { Style = style, BlockSize = 3072, StreetWidth = 448, PlotWidth = 1024, PlotDepth = 1024, Irregularity = 0.0f },
		DistrictStyle.OldTown => new() { Style = style, BlockSize = 1024, StreetWidth = 192, PlotWidth = 288, PlotDepth = 384, Irregularity = 0.3f },
		DistrictStyle.Coastal => new() { Style = style, BlockSize = 1280, StreetWidth = 224, PlotWidth = 320, PlotDepth = 416, Irregularity = 0.15f },
		_ => new() { Style = style, BlockSize = 2048, StreetWidth = 384, PlotWidth = 448, PlotDepth = 512, Irregularity = 0.0f },
	};

	/// <summary>
	/// Share of each use per style. Shops prefer corners, see <see cref="PickUse"/>.
	/// </summary>
	static (PlotUse Use, float Weight)[] Mix( DistrictStyle style ) => style switch
	{
		DistrictStyle.Industrial => [(PlotUse.Warehouse, 6), (PlotUse.Parking, 2), (PlotUse.Green, 1)],
		DistrictStyle.OldTown => [(PlotUse.House, 9), (PlotUse.Green, 1)],
		DistrictStyle.Coastal => [(PlotUse.House, 10), (PlotUse.Green, 1)],
		_ => [(PlotUse.House, 6.5f), (PlotUse.Apartment, 3), (PlotUse.Green, 1)],
	};

	const int MaxCells = 4096;

	public static DistrictPlan Plan( IReadOnlyList<Vector2> outline, DistrictLayoutSettings s )
	{
		var plan = new DistrictPlan();
		if ( outline is null || outline.Count < 3 )
			return plan;
		var ring = outline.ToList();
		if ( Area( ring ) < 0.0f )
			ring.Reverse();
		if ( Area( ring ) < 1.0f )
			return plan;
		var street = MathF.Max( s.StreetWidth, 16.0f );
		var stepX = MathF.Max( s.BlockSize, 64.0f ) * Math.Clamp( s.BlockAspect, .25f, 6 ) + street;
		var stepY = MathF.Max( s.BlockSize, 64.0f ) + street;
		var step = MathF.Min( stepX, stepY );
		var rad = s.Angle.DegreeToRadian();
		var u = new Vector2( MathF.Cos( rad ), MathF.Sin( rad ) );
		var v = new Vector2( -u.y, u.x );
		var jitter = Math.Clamp( s.Irregularity, 0.0f, 0.4f ) * step * 0.5f;
		var minU = ring.Min( p => Dot( p, u ) ) - stepX;
		var maxU = ring.Max( p => Dot( p, u ) ) + stepX;
		var minV = ring.Min( p => Dot( p, v ) ) - stepY;
		var maxV = ring.Max( p => Dot( p, v ) ) + stepY;
		var i0 = (int)MathF.Floor( minU / stepX );
		var j0 = (int)MathF.Floor( minV / stepY );
		var ni = (int)MathF.Ceiling( maxU / stepX ) - i0;
		var nj = (int)MathF.Ceiling( maxV / stepY ) - j0;
		if ( ni * nj > MaxCells )
			return plan;
		Vector2 Node( int i, int j )
		{
			var x = (i0 + i) * stepX + jitter * Noise( s.Seed, i0 + i, j0 + j, 0 );
			var y = (j0 + j) * stepY + jitter * Noise( s.Seed, i0 + i, j0 + j, 1 );
			return u * x + v * y;
		}

		// Grid edges that border at least one block become streets.
		var streetEdges = new HashSet<(int, int, int, int)>();
		var cells = new List<(List<Vector2> Block, List<Vector2> Inset, int Index)>();
		for ( var i = 0; i < ni; i++ )
		{
			for ( var j = 0; j < nj; j++ )
			{
				var quad = new List<Vector2>
				{
					Node( i, j ),
					Node( i + 1, j ),
					Node( i + 1, j + 1 ),
					Node( i, j + 1 )
				};
				if ( Area( quad ) <= 0.0f )
					continue;
				var inset = Inset( quad, street * 0.5f );
				if ( inset is null )
					continue;
				var block = Clip( ring, inset );
				if ( block.Count < 3 || Area( block ) < Area( inset ) * 0.15f )
					continue;
				var index = plan.Blocks.Count;
				plan.Blocks.Add( new DistrictBlock( block ) );
				(int, int, int, int)[] sides = [(i, j, i + 1, j), (i + 1, j, i + 1, j + 1), (i, j + 1, i + 1, j + 1), (i, j, i, j + 1)];
				for ( var k = 0; k < 4; k++ )
				{
					if ( OnLine( block, inset[k], inset[(k + 1) % 4] ) )
						streetEdges.Add( sides[k] );
				}

				cells.Add( (block, inset, index) );
			}
		}

		// Streets: grid edges kept inside the outline.
		var arms = new Dictionary<(int, int), List<Vector2>>();
		foreach ( var(ai, aj, bi, bj)in streetEdges )
		{
			var a = Node( ai, aj );
			var b = Node( bi, bj );
			foreach ( var(from, to)in Inside( ring, a, b ) )
			{
				if ( (to - from).Length < street * 0.5f )
					continue;
				plan.Streets.Add( new DistrictStreet( from, to, street ) );
			}

			if ( Contains( ring, a ) )
				Arm( arms, (ai, aj), (b - a).Normal );
			if ( Contains( ring, b ) )
				Arm( arms, (bi, bj), (a - b).Normal );
		}

		foreach ( var((i, j), list)in arms.OrderBy( x => x.Key ) )
		{
			if ( list.Count >= 3 )
				plan.Junctions.Add( new DistrictJunction( Node( i, j ), list ) );
		}

		// Plots last: a block side only counts as street side where a street was kept. Streets
		// beyond the outline are cut off, the plots there would face nothing.
		foreach ( var(block, inset, index)in cells )
			AddPlots( plan, block, inset, index, s );
		return plan;
	}

	static void Arm( Dictionary<(int, int), List<Vector2>> arms, (int, int) key, Vector2 direction )
	{
		if ( !arms.TryGetValue( key, out var list ) ) arms[key] = list = [];
		list.Add( direction );
	}

	/// <summary>
	/// Plots along each street edge of a block. A corner belongs to the edge before it. The next edge
	/// starts far enough from the corner that its plots clear those of the edge before, for any angle.
	/// </summary>
	static void AddPlots( DistrictPlan plan, List<Vector2> block, List<Vector2> inset, int index, DistrictLayoutSettings s )
	{
		var count = block.Count;
		var streetSide = new bool[count];
		var half = s.StreetWidth * 0.5f;
		bool AtStreet( Vector2 p ) => MathF.Abs( ToStreet( plan, p ) - MathF.Max( half, 8.0f ) ) < 1.5f;
		for ( var e = 0; e < count; e++ )
			streetSide[e] = OnStreet( block[e], block[(e + 1) % count], inset ) && AtStreet( (block[e] + block[(e + 1) % count]) * 0.5f );

		// Across the block, measured square to its sides, not along them.
		var area = Area( inset );
		var extent = MathF.Min( area / Width( inset, 0 ), area / Width( inset, 1 ) );
		var depth = MathF.Min( MathF.Max( s.PlotDepth, 32.0f ), extent * 0.5f );
		var width = MathF.Max( s.PlotWidth, 32.0f );
		var made = new List<(List<Vector2> Ring, List<Vector2> Quad)>();

		for ( var e = 0; e < count; e++ )
		{
			if ( !streetSide[e] ) continue;

			var a = block[e];
			var b = block[(e + 1) % count];
			var length = (b - a).Length;
			var dir = (b - a) / length;
			var inward = new Vector2( -dir.y, dir.x );
			var start = 0.0f;
			if ( streetSide[(e + count - 1) % count] )
			{
				var before = block[(e + count - 1) % count];
				var prev = (a - before).Normal;
				var turn = MathF.Atan2( Cross( prev, dir ), Dot( prev, dir ) );
				start = turn <= 0.0f ? 0.0f : CornerClearance( turn, depth );
			}
			var usable = length - start;
			if ( usable < width * 0.6f ) continue;

			var n = Math.Max( 1, (int)MathF.Round( usable / width ) );
			var w = usable / n;

			for ( var p = 0; p < n; p++ )
			{
				var p0 = a + dir * (start + p * w);
				var p1 = p0 + dir * w;
				var quad = new List<Vector2> { p0, p1, p1 + inward * depth, p0 + inward * depth };
				var plot = Clip( block, quad );
				if ( plot.Count < 3 || Area( plot ) < w * depth * 0.4f ) continue;
				if ( !AtStreet( (p0 + p1) * 0.5f ) ) continue;

				// Where a short side cut the corner rule short, the later plot gives way.
				if ( made.Any( x => Area( Clip( plot, x.Quad ) ) > Area( plot ) * 0.01f ) ) continue;

				made.Add( (plot, quad) );
				var corner = (p == 0 && start == 0.0f) || p == n - 1;
				var use = PickUse( s, index, e, p, corner );
				plan.Plots.Add( new DistrictPlot( plot, (p0 + p1) * 0.5f, -inward, w, depth, use, index ) );
			}
		}
	}

	/// <summary>
	/// How far from a corner the plots of the next side start, so they clear the plots of the side
	/// before. <paramref name="turn"/> is the left turn at the corner in radians, between 0 and pi.
	/// </summary>
	static float CornerClearance( float turn, float depth )
	{
		var sin = MathF.Sin( turn );
		var cos = MathF.Cos( turn );
		if ( sin < 1e-4f ) return float.MaxValue;

		// Beyond the depth of the plots before, or behind their end square to the side before.
		var past = depth * MathF.Max( 1.0f, 1.0f - cos ) / sin;
		var behind = cos > 1e-4f ? depth * sin / cos : float.MaxValue;
		return MathF.Min( past, behind );
	}

	static float ToStreet( DistrictPlan plan, Vector2 p )
	{
		var best = float.MaxValue;
		foreach ( var x in plan.Streets )
		{
			var d = x.B - x.A;
			var t = Math.Clamp( Dot( p - x.A, d ) / MathF.Max( Dot( d, d ), 1e-6f ), 0.0f, 1.0f );
			best = MathF.Min( best, (p - (x.A + d * t)).Length );
		}
		return best;
	}

	static PlotUse PickUse( DistrictLayoutSettings s, int block, int edge, int plot, bool corner )
	{
		var mix = Mix( s.Style );
		var roll = (Noise( s.Seed, block * 97 + edge, plot, 7 ) + 1.0f) * 0.5f;


		var total = mix.Sum( x => x.Weight );
		var pick = roll * total;
		foreach ( var (use, weight) in mix )
		{
			if ( pick < weight ) return use;
			pick -= weight;
		}

		return mix[^1].Use;
	}

	/// <summary>
	/// A stable value between -1 and 1 for a grid node, the same on every machine.
	/// </summary>
	static float Noise( int seed, int i, int j, int salt )
	{
		unchecked
		{
			var h = (uint)seed * 0x9E3779B1u ^ (uint)i * 0x85EBCA77u ^ (uint)j * 0xC2B2AE3Du ^ (uint)salt * 0x27D4EB2Fu;
			h ^= h >> 15; h *= 0x2C1B3C6Du; h ^= h >> 12; h *= 0x297A2D39u; h ^= h >> 15;
			return (h & 0xFFFFFF) / (float)0xFFFFFF * 2.0f - 1.0f;
		}
	}

	public static float Area( IReadOnlyList<Vector2> ring )
	{
		// Measured from the first corner: with world sized coordinates the products would
		// swallow the small differences that make up the area.
		if ( ring.Count < 3 ) return 0.0f;
		var o = ring[0];
		var area = 0.0f;
		for ( var i = 1; i + 1 < ring.Count; i++ ) area += Cross( ring[i] - o, ring[i + 1] - o );
		return area * 0.5f;
	}

	public static bool Contains( IReadOnlyList<Vector2> ring, Vector2 p )
	{
		var inside = false;
		for ( int i = 0, j = ring.Count - 1; i < ring.Count; j = i++ )
		{
			var a = ring[i];
			var b = ring[j];
			if ( (a.y > p.y) != (b.y > p.y) && p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x ) inside = !inside;
		}
		return inside;
	}

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

	static float Width( List<Vector2> quad, int axis ) =>
		((quad[axis + 1] - quad[axis]).Length + (quad[(axis + 3) % 4] - quad[(axis + 2) % 4]).Length) * 0.5f;

	/// <summary>
	/// A convex counter clockwise polygon moved inward by a distance on every edge. Null when it vanishes.
	/// </summary>
	static List<Vector2> Inset( List<Vector2> poly, float distance )
	{
		var count = poly.Count;
		var result = new List<Vector2>( count );

		for ( var i = 0; i < count; i++ )
		{
			var a0 = poly[(i + count - 1) % count];
			var a1 = poly[i];
			var b1 = poly[(i + 1) % count];
			var da = (a1 - a0).Normal;
			var db = (b1 - a1).Normal;
			var pa = a0 + new Vector2( -da.y, da.x ) * distance;
			var pb = a1 + new Vector2( -db.y, db.x ) * distance;
			var denom = Cross( da, db );
			if ( MathF.Abs( denom ) < 1e-5f ) return null;
			var t = Cross( pb - pa, db ) / denom;
			result.Add( pa + da * t );
		}

		return Area( result ) > 1.0f ? result : null;
	}

	/// <summary>
	/// Sutherland-Hodgman: the part of <paramref name="subject"/> inside the convex counter clockwise <paramref name="clip"/>.
	/// </summary>
	public static List<Vector2> Clip( IReadOnlyList<Vector2> subject, IReadOnlyList<Vector2> clip )
	{
		var output = subject.ToList();

		for ( var c = 0; c < clip.Count && output.Count > 0; c++ )
		{
			var a = clip[c];
			var b = clip[(c + 1) % clip.Count];
			var input = output;
			output = new List<Vector2>( input.Count + 2 );

			for ( var i = 0; i < input.Count; i++ )
			{
				var p = input[i];
				var q = input[(i + 1) % input.Count];
				var pIn = Cross( b - a, p - a ) >= 0.0f;
				var qIn = Cross( b - a, q - a ) >= 0.0f;

				if ( pIn ) output.Add( p );
				if ( pIn != qIn )
				{
					var d = q - p;
					var t = Cross( b - a, a - p ) / Cross( b - a, d );
					output.Add( p + d * t );
				}
			}
		}

		// Drop repeated points left by edges that run along the clip line.
		var clean = new List<Vector2>( output.Count );
		foreach ( var p in output )
		{
			if ( clean.Count == 0 || (p - clean[^1]).Length > 0.01f ) clean.Add( p );
		}
		if ( clean.Count > 1 && (clean[0] - clean[^1]).Length <= 0.01f ) clean.RemoveAt( clean.Count - 1 );

		// A concave subject leaves spikes without area along a clip edge: the outline runs out and
		// straight back. Such a corner is dropped until none is left.
		for ( var changed = true; changed && clean.Count >= 3; )
		{
			changed = false;
			for ( var i = 0; i < clean.Count && clean.Count >= 3; i++ )
			{
				var a = clean[(i + clean.Count - 1) % clean.Count];
				var b = clean[i];
				var c = clean[(i + 1) % clean.Count];
				var ab = b - a;
				var bc = c - b;
				var la = ab.Length;
				var lb = bc.Length;
				if ( la < 0.01f || lb < 0.01f || (MathF.Abs( Cross( ab, bc ) ) / (la * lb) < 1e-3f && Dot( ab, bc ) < 0.0f) )
				{
					clean.RemoveAt( i );
					changed = true;
					i--;
				}
			}
		}

		return clean.Count >= 3 ? clean : [];
	}

	/// <summary>
	/// True when the edge of a block lies on one of the street edges of its cell.
	/// </summary>
	static bool OnStreet( Vector2 a, Vector2 b, List<Vector2> inset )
	{
		for ( var k = 0; k < inset.Count; k++ )
		{
			if ( OnSegmentLine( a, inset[k], inset[(k + 1) % inset.Count] ) && OnSegmentLine( b, inset[k], inset[(k + 1) % inset.Count] ) ) return true;
		}
		return false;
	}

	static bool OnLine( List<Vector2> block, Vector2 a, Vector2 b )
	{
		for ( var e = 0; e < block.Count; e++ )
		{
			if ( OnSegmentLine( block[e], a, b ) && OnSegmentLine( block[(e + 1) % block.Count], a, b ) && (block[(e + 1) % block.Count] - block[e]).Length > 1.0f ) return true;
		}
		return false;
	}

	static bool OnSegmentLine( Vector2 p, Vector2 a, Vector2 b )
	{
		var d = b - a;
		var length = d.Length;
		if ( length < 1e-3f ) return false;
		return MathF.Abs( Cross( d, p - a ) ) / length < 0.5f;
	}

	/// <summary>
	/// The pieces of the segment a to b that lie inside the outline.
	/// </summary>
	public static IEnumerable<(Vector2, Vector2)> Inside( List<Vector2> ring, Vector2 a, Vector2 b )
	{
		var cuts = new List<float>
		{
			0.0f,
			1.0f
		};
		var d = b - a;
		for ( var i = 0; i < ring.Count; i++ )
		{
			var p = ring[i];
			var e = ring[(i + 1) % ring.Count] - p;
			var denom = Cross( d, e );
			if ( MathF.Abs( denom ) < 1e-6f )
				continue;
			var t = Cross( p - a, e ) / denom;
			var s = Cross( p - a, d ) / denom;
			if ( t > 0.0f && t < 1.0f && s >= 0.0f && s <= 1.0f )
				cuts.Add( t );
		}

		cuts.Sort();
		for ( var i = 0; i + 1 < cuts.Count; i++ )
		{
			var from = a + d * cuts[i];
			var to = a + d * cuts[i + 1];
			if ( Contains( ring, (from + to) * 0.5f ) )
				yield return (from, to);
		}
	}
}