using System;
using System.Collections;
using System.Collections.Immutable;

namespace HC3.Terrain;

#nullable enable

/// <summary>
/// Describes how a <see cref="TileSlope"/> is triangulated.
/// Some slopes aren't planar, so this decides which diagonal the
/// crease is on.
/// </summary>
public enum TileTriangulation
{
	/// <summary>
	/// Tile is split between <see cref="TileCorner.XMinYMin"/> and <see cref="TileCorner.XMaxYMax"/>.
	/// </summary>
	Default,

	/// <summary>
	/// Tile is split between <see cref="TileCorner.XMaxYMin"/> and <see cref="TileCorner.XMinYMax"/>.
	/// </summary>
	Flipped
}

/// <summary>
/// Describes the relative heights of each corner of a tile.
/// Heights are relative to the lowest corner, so at least one corner is guaranteed to have a relative height of <c>0</c>.
/// </summary>
public readonly struct TileSlope : IEquatable<TileSlope>, IComparable<TileSlope>
{
	internal const int SizeBytes = sizeof( ushort );

	private readonly ushort _encoded;

	private const int BitsPerCorner = (SizeBytes << 3) >> 2;
	private const ushort CornerBitMask = (1 << BitsPerCorner) - 1;

	/// <summary>
	/// Highest height of a corner in a slope relative to the lowest.
	/// </summary>
	public const int MaxCornerHeightOffset = CornerBitMask;

	/// <summary>
	/// Level, flat ground.
	/// </summary>
	public static TileSlope LevelGround => default;

	/// <summary>
	/// All legal slopes.
	/// </summary>
	public static IReadOnlyList<TileSlope> All { get; } = Enumerable.Range( 0, ushort.MaxValue )
		.Select( x => new TileSlope( (ushort)x ) )
		.Where( x => x.MinHeightOffset == 0 )
		.ToImmutableArray();

	/// <summary>
	/// Will always be 0 for legal slopes, just used for building <see cref="All"/>.
	/// </summary>
	private int MinHeightOffset => Math.Min(
		Math.Min( GetHeightOffset( TileCorner.XMinYMin ), GetHeightOffset( TileCorner.XMaxYMin ) ),
		Math.Min( GetHeightOffset( TileCorner.XMinYMax ), GetHeightOffset( TileCorner.XMaxYMax ) ) );

	/// <summary>
	/// Relative height of the highest corner of this slope.
	/// </summary>
	public int MaxHeightOffset => Math.Max(
		Math.Max( GetHeightOffset( TileCorner.XMinYMin ), GetHeightOffset( TileCorner.XMaxYMin ) ),
		Math.Max( GetHeightOffset( TileCorner.XMinYMax ), GetHeightOffset( TileCorner.XMaxYMax ) ) );

	/// <summary>
	/// True if all corners are at the same height.
	/// </summary>
	public bool IsLevel => this == LevelGround;

	/// <summary>
	/// Describes how this slope is triangulated.
	/// Some slopes aren't planar, so this decides which diagonal the
	/// crease is on.
	/// </summary>
	public TileTriangulation Triangulation
	{
		get
		{
			var diag0 = GetHeightOffset( TileCorner.XMaxYMax ) - GetHeightOffset( TileCorner.XMinYMin );
			var diag1 = GetHeightOffset( TileCorner.XMaxYMin ) - GetHeightOffset( TileCorner.XMinYMax );

			return Math.Abs( diag0 ) < Math.Abs( diag1 ) ? TileTriangulation.Default : TileTriangulation.Flipped;
		}
	}

	/// <summary>
	/// True if opposite edges are parallel.
	/// </summary>
	public bool IsFlat => GetEdgeGradient( TileEdge.XMin ) == GetEdgeGradient( TileEdge.XMax )
		&& GetEdgeGradient( TileEdge.YMin ) == GetEdgeGradient( TileEdge.YMax );

	private TileSlope( ushort encoded )
	{
		_encoded = encoded;
	}

	/// <summary>
	/// Gets the height of a particular corner, relative to the lowest corner.
	/// </summary>
	public int GetHeightOffset( TileCorner corner )
	{
		var shift = (int)corner * BitsPerCorner;

		return (_encoded & (CornerBitMask << shift)) >> shift;
	}

	/// <summary>
	/// Gets the height offset of a relative position where <c>(0,0)</c> is the height at <see cref="TileCorner.XMinYMin"/>
	/// and <c>(1,1)</c> is the height at <see cref="TileCorner.XMaxYMax"/>. Position is clamped on each axis.
	/// </summary>
	public float GetHeightOffset( Vector2 position )
	{
		position = Vector2.Max( 0, Vector2.Min( 1, position ) );

		Span<int> corners = stackalloc int[4];
		GetHeightOffsets( corners );

		if ( Triangulation == TileTriangulation.Flipped )
		{
			// Flip everything horizontally if triangulation is flipped,
			// so crease is always from (0,0) to (1,1), in other words x == y

			position.x = 1f - position.x;

			// Swap heights of corners

			(corners[(int)TileCorner.XMinYMin], corners[(int)TileCorner.XMaxYMin])
				= (corners[(int)TileCorner.XMaxYMin], corners[(int)TileCorner.XMinYMin]);

			(corners[(int)TileCorner.XMinYMax], corners[(int)TileCorner.XMaxYMax])
				= (corners[(int)TileCorner.XMaxYMax], corners[(int)TileCorner.XMinYMax]);
		}

		// Each triangle has its own 2D gradient, we'll find it by getting
		// the 1D gradients of the axis aligned edges

		Vector2 gradient = default;

		// Crease between the two triangles is x == y,
		// so one triangle is x > y and the other is x < y

		if ( position.x < position.y )
		{
			gradient.x = corners[(int)TileCorner.XMaxYMax] - corners[(int)TileCorner.XMinYMax];
			gradient.y = corners[(int)TileCorner.XMinYMax] - corners[(int)TileCorner.XMinYMin];
		}
		else
		{
			gradient.x = corners[(int)TileCorner.XMaxYMin] - corners[(int)TileCorner.XMinYMin];
			gradient.y = corners[(int)TileCorner.XMaxYMax] - corners[(int)TileCorner.XMaxYMin];
		}

		// Height relative to the (0,0) corner, increasing by
		// gradient as we travel towards (1,1).

		return corners[(int)TileCorner.XMinYMin] + Vector2.Dot( position, gradient );
	}

	/// <summary>
	/// Get the total absolute vertical distances of each corner to the given <paramref name="other"/> slope.
	/// </summary>
	/// <param name="other">Slope to compare to.</param>
	/// <param name="tileHeightOffset">Relative height of the other tile to this one.</param>
	public int GetTotalDistance( TileSlope other, int tileHeightOffset = 0 )
	{
		var sum = 0;

		sum += Math.Abs( GetHeightOffset( TileCorner.XMinYMin ) - other.GetHeightOffset( TileCorner.XMinYMin ) - tileHeightOffset );
		sum += Math.Abs( GetHeightOffset( TileCorner.XMaxYMin ) - other.GetHeightOffset( TileCorner.XMaxYMin ) - tileHeightOffset );
		sum += Math.Abs( GetHeightOffset( TileCorner.XMinYMax ) - other.GetHeightOffset( TileCorner.XMinYMax ) - tileHeightOffset );
		sum += Math.Abs( GetHeightOffset( TileCorner.XMaxYMax ) - other.GetHeightOffset( TileCorner.XMaxYMax ) - tileHeightOffset );

		return sum;
	}

	/// <summary>
	/// Get the minimum distance when subtracting corner heights of <paramref name="other"/> from this slope's corners.
	/// </summary>
	public int GetMinDistance( TileSlope other )
	{
		var min = int.MaxValue;

		min = Math.Min( min, GetHeightOffset( TileCorner.XMinYMin ) - other.GetHeightOffset( TileCorner.XMinYMin ) );
		min = Math.Min( min, GetHeightOffset( TileCorner.XMaxYMin ) - other.GetHeightOffset( TileCorner.XMaxYMin ) );
		min = Math.Min( min, GetHeightOffset( TileCorner.XMinYMax ) - other.GetHeightOffset( TileCorner.XMinYMax ) );
		min = Math.Min( min, GetHeightOffset( TileCorner.XMaxYMax ) - other.GetHeightOffset( TileCorner.XMaxYMax ) );

		return min;
	}

	/// <summary>
	/// Get the maximum distance when subtracting corner heights of <paramref name="other"/> from this slope's corners.
	/// </summary>
	public int GetMaxDistance( TileSlope other )
	{
		var max = int.MinValue;

		max = Math.Max( max, GetHeightOffset( TileCorner.XMinYMin ) - other.GetHeightOffset( TileCorner.XMinYMin ) );
		max = Math.Max( max, GetHeightOffset( TileCorner.XMaxYMin ) - other.GetHeightOffset( TileCorner.XMaxYMin ) );
		max = Math.Max( max, GetHeightOffset( TileCorner.XMinYMax ) - other.GetHeightOffset( TileCorner.XMinYMax ) );
		max = Math.Max( max, GetHeightOffset( TileCorner.XMaxYMax ) - other.GetHeightOffset( TileCorner.XMaxYMax ) );

		return max;
	}

	public void GetHeightOffsets( Span<int> heights )
	{
		heights[(int)TileCorner.XMinYMin] = GetHeightOffset( TileCorner.XMinYMin );
		heights[(int)TileCorner.XMaxYMin] = GetHeightOffset( TileCorner.XMaxYMin );
		heights[(int)TileCorner.XMinYMax] = GetHeightOffset( TileCorner.XMinYMax );
		heights[(int)TileCorner.XMaxYMax] = GetHeightOffset( TileCorner.XMaxYMax );
	}

	public int GetEdgeGradient( TileEdge edge )
	{
		var (min, max) = edge.GetCorners();

		return GetHeightOffset( max ) - GetHeightOffset( min );
	}

	public Vector2Int GetGradients()
	{
		if ( MaxHeightOffset == 0 ) return 0;

		var xMin = Math.Max( GetHeightOffset( TileCorner.XMinYMin ), GetHeightOffset( TileCorner.XMinYMax ) );
		var xMax = Math.Max( GetHeightOffset( TileCorner.XMaxYMin ), GetHeightOffset( TileCorner.XMaxYMax ) );

		var yMin = Math.Max( GetHeightOffset( TileCorner.XMinYMin ), GetHeightOffset( TileCorner.XMaxYMin ) );
		var yMax = Math.Max( GetHeightOffset( TileCorner.XMinYMax ), GetHeightOffset( TileCorner.XMaxYMax ) );

		return new Vector2Int( xMax - xMin, yMax - yMin );
	}

	public bool Equals( TileSlope other ) => _encoded == other._encoded;
	public override bool Equals( object? obj ) => obj is TileSlope other && Equals( other );

	public override int GetHashCode() => _encoded;

	public int CompareTo( TileSlope other ) => _encoded.CompareTo( other._encoded );

	public override string ToString() =>
		$"[{GetHeightOffset( TileCorner.XMinYMin )}, " +
		$"{GetHeightOffset( TileCorner.XMaxYMin )}, " +
		$"{GetHeightOffset( TileCorner.XMinYMax )}, " +
		$"{GetHeightOffset( TileCorner.XMaxYMax )}]";

	public static bool operator ==( TileSlope a, TileSlope b ) => a.Equals( b );
	public static bool operator !=( TileSlope a, TileSlope b ) => !a.Equals( b );

	public static TileSlope FromCornerHeights( ReadOnlySpan<int> heights )
	{
		ArgumentOutOfRangeException.ThrowIfNotEqual( heights.Length, 4, nameof( heights ) );

		ArgumentOutOfRangeException.ThrowIfLessThan( heights[0], 0, nameof( heights ) );
		ArgumentOutOfRangeException.ThrowIfLessThan( heights[1], 0, nameof( heights ) );
		ArgumentOutOfRangeException.ThrowIfLessThan( heights[2], 0, nameof( heights ) );
		ArgumentOutOfRangeException.ThrowIfLessThan( heights[3], 0, nameof( heights ) );

		ArgumentOutOfRangeException.ThrowIfGreaterThan( heights[0], MaxCornerHeightOffset, nameof( heights ) );
		ArgumentOutOfRangeException.ThrowIfGreaterThan( heights[1], MaxCornerHeightOffset, nameof( heights ) );
		ArgumentOutOfRangeException.ThrowIfGreaterThan( heights[2], MaxCornerHeightOffset, nameof( heights ) );
		ArgumentOutOfRangeException.ThrowIfGreaterThan( heights[3], MaxCornerHeightOffset, nameof( heights ) );

		if ( heights[0] != 0 && heights[1] != 0 && heights[2] != 0 && heights[3] != 0 )
		{
			throw new ArgumentException( "Expected at least one corner to be at height 0.", nameof( heights ) );
		}

		return new TileSlope( (ushort)(heights[0] | (heights[1] << BitsPerCorner) | (heights[2] << (BitsPerCorner * 2)) | (heights[3] << (BitsPerCorner * 3))) );
	}
}

public sealed class SlopeTileset : IEnumerable<TileSlope>
{
	private readonly ImmutableHashSet<TileSlope> _slopes;
	private readonly Dictionary<TileSlope, (TileSlope Slope, int Offset)> _below = new();
	private readonly Dictionary<TileSlope, (TileSlope Slope, int Offset)> _above = new();

	public int Count => _slopes.Count;

	public SlopeTileset( IEnumerable<TileSlope> slopes )
	{
		_slopes = slopes
			.Distinct()
			.Order()
			.ToImmutableHashSet();
	}

	public bool Contains( TileSlope slope ) => _slopes.Contains( slope );

	public TerrainTile FromCornerHeights( ReadOnlySpan<int> cornerHeights, TilePaint paint )
	{
		ArgumentOutOfRangeException.ThrowIfNotEqual( cornerHeights.Length, 4, nameof( cornerHeights ) );

		var min = cornerHeights[0];
		var max = cornerHeights[0];

		for ( var i = 1; i < 4; ++i )
		{
			min = Math.Min( min, cornerHeights[i] );
			max = Math.Max( max, cornerHeights[i] );
		}

		min = Math.Clamp( min, 0, ushort.MaxValue );
		max = Math.Clamp( max, 0, ushort.MaxValue );

		if ( min == max )
		{
			// Easy common case: no slope

			return new TerrainTile( (ushort)min, TileSlope.LevelGround, paint );
		}

		Span<int> relativeHeights = stackalloc int[4];

		for ( var i = 0; i < 4; ++i )
		{
			relativeHeights[i] = Math.Clamp( cornerHeights[i] - min, 0, TileSlope.MaxCornerHeightOffset );
		}

		var slope = TileSlope.FromCornerHeights( relativeHeights );

		return FindClosestBelow( new TerrainTile( (ushort)min, slope, paint ) );
	}

	private (TileSlope Slope, int Offset) FindBelowUncached( TileSlope slope )
	{
		var bestSlope = TileSlope.LevelGround;
		var bestOffset = 0;
		var bestDistance = int.MaxValue;

		foreach ( var other in _slopes )
		{
			var offset = -other.GetMaxDistance( slope );
			var distance = slope.GetTotalDistance( other, offset );

			if ( distance < bestDistance )
			{
				bestSlope = other;
				bestOffset = offset;
				bestDistance = distance;
			}
		}

		return (bestSlope, bestOffset);
	}

	private (TileSlope Slope, int Offset) FindAboveUncached( TileSlope slope )
	{
		var bestSlope = TileSlope.LevelGround;
		var bestOffset = 0;
		var bestDistance = int.MaxValue;

		foreach ( var other in _slopes )
		{
			var offset = -other.GetMinDistance( slope );
			var distance = slope.GetTotalDistance( other, offset );

			if ( distance < bestDistance )
			{
				bestSlope = other;
				bestOffset = offset;
				bestDistance = distance;
			}
		}

		return (bestSlope, bestOffset);
	}

	/// <summary>
	/// Creates a tile using this tileset that closest matches the given tile, while not going above
	/// any of its corner heights.
	/// </summary>
	public TerrainTile FindClosestBelow( TerrainTile tile )
	{
		if ( _slopes.Contains( tile.Slope ) ) return tile;

		if ( !_below.TryGetValue( tile.Slope, out var below ) )
		{
			_below[tile.Slope] = below = FindBelowUncached( tile.Slope );
		}

		return tile.MinHeight + below.Offset < 0
			? TerrainTile.LevelGround( 0 )
			: new TerrainTile( (ushort)(tile.MinHeight + below.Offset), below.Slope, tile.Paint );
	}

	/// <summary>
	/// Creates a tile using this tileset that closest matches the given tile, while not going below
	/// any of its corner heights.
	/// </summary>
	public TerrainTile FindClosestAbove( TerrainTile tile )
	{
		if ( _slopes.Contains( tile.Slope ) ) return tile;

		if ( !_above.TryGetValue( tile.Slope, out var above ) )
		{
			_above[tile.Slope] = above = FindAboveUncached( tile.Slope );
		}

		return new TerrainTile( (ushort)(tile.MinHeight + above.Offset), above.Slope, tile.Paint );
	}

	public static SlopeTileset FromMaxGradients( IEnumerable<TileSlope> slopes, int maxGradientX, int maxGradientY )
	{
		return new SlopeTileset( slopes
			.Where( slope =>
			{
				if ( !slope.IsFlat ) return false;

				if ( Math.Abs( slope.GetEdgeGradient( TileEdge.YMin ) ) > maxGradientX ) return false;
				if ( Math.Abs( slope.GetEdgeGradient( TileEdge.XMin ) ) > maxGradientY ) return false;

				return true;
			} ) );
	}

	public static SlopeTileset FromMaxEdgeGradient( IEnumerable<TileSlope> slopes, int maxGradient )
	{
		return new SlopeTileset( slopes
			.Where( slope =>
			{
				Span<int> c = stackalloc int[4];

				slope.GetHeightOffsets( c );

				if ( Math.Abs( c[1] - c[0] ) > maxGradient ) return false;
				if ( Math.Abs( c[2] - c[0] ) > maxGradient ) return false;
				if ( Math.Abs( c[3] - c[1] ) > maxGradient ) return false;
				if ( Math.Abs( c[3] - c[2] ) > maxGradient ) return false;

				return true;
			} ) );
	}

	public IEnumerator<TileSlope> GetEnumerator() => _slopes.GetEnumerator();
	IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}