using System;
using System.Collections.Generic;
using static Diamonds.DiamondBoard;

namespace Diamonds;

/// <summary>Side-connected color bonds and rigid-group gravity.</summary>
public static class DiamondMatching
{
	const float Epsilon = 0.01f;

	/// <summary>Matching and bonding both require a full sloped side, never a tip.</summary>
	public static bool Touching( Diamond a, Diamond b ) =>
		MathF.Abs( MathF.Abs( a.Lane - b.Lane ) - 1 ) < Epsilon / Width
		&& MathF.Abs( MathF.Abs( a.Y - b.Y ) - Height * 0.5f ) < Epsilon;

	public readonly record struct CellMove( int Index, Diamond From, Diamond To );

	/// <summary>All cells share one continuous translation and one animation clock.</summary>
	public sealed record SettlementMove( IReadOnlyList<CellMove> Cells )
	{
		public bool IsSlide => Cells[0].From.Lane != Cells[0].To.Lane;
		// Sharper acceleration across the whole slope, with a brisk finish.
		// Crossing another lattice position must not restart the easing clock.
		// Root-scaled fall time keeps acceleration consistent as drop height grows,
		// so long falls build speed instead of stretching to the same terminal speed.
		public float Duration => IsSlide ? 0.18f * MathF.Sqrt( MathF.Abs( Cells[0].To.Lane - Cells[0].From.Lane ) )
			: MathF.Max( 0.14f, 0.2f * MathF.Pow( (Cells[0].To.Y - Cells[0].From.Y) / Height, 1 / EasePower ) );
		public float EasePower => IsSlide ? 2.8f : 2.2f;
		public float Blend( float t ) => MathF.Pow( Math.Clamp( t, 0, 1 ), EasePower );
		public float VelocityScale( float t, float speed ) => EasePower * MathF.Pow( Math.Clamp( t, 0, 1 ), EasePower - 1 ) * speed / Duration;
	}

	public static List<List<int>> FindGroups( IReadOnlyList<Diamond> diamonds )
		=> FindGroups( diamonds, -1 );

	internal static List<List<int>> FindGroups( IReadOnlyList<Diamond> diamonds, int incomingStart )
	{
#if STANDALONE
#endif
		var groups = new List<List<int>>();
		var visited = new bool[diamonds.Count];
		for ( int start = 0; start < diamonds.Count; start++ )
		{
			if ( visited[start] ) continue;
			var group = new List<int> { start };
			visited[start] = true;
			for ( int head = 0; head < group.Count; head++ )
			{
				var current = diamonds[group[head]];
				for ( int next = 0; next < diamonds.Count; next++ )
				{
					// A newly landed piece has not bonded to the existing stack yet.
					if ( incomingStart >= 0 && (group[head] >= incomingStart) != (next >= incomingStart) ) continue;
					if ( visited[next] || diamonds[next].ColorIndex != current.ColorIndex || !Touching( current, diamonds[next] ) ) continue;
					visited[next] = true;
					group.Add( next );
				}
			}
			groups.Add( group );
		}
		return groups;
	}

	/// <summary>Reindex surviving bonds after destruction and split any severed connections.
	/// Never merge different old groups because they happen to touch mid-settlement.</summary>
	public static List<List<int>> SurvivingGroups( IReadOnlyList<Diamond> diamonds,
		IReadOnlyList<IReadOnlyList<int>> oldGroups, IReadOnlyList<int> remap )
	{
		var result = new List<List<int>>();
		foreach ( var old in oldGroups )
		{
			var remaining = new HashSet<int>();
			foreach ( int index in old ) if ( remap[index] >= 0 ) remaining.Add( remap[index] );
			while ( remaining.Count > 0 )
			{
				int first = -1;
				foreach ( int index in remaining ) { first = index; break; }
				remaining.Remove( first );
				var group = new List<int> { first };
				for ( int head = 0; head < group.Count; head++ )
				{
					var attached = new List<int>();
					foreach ( int index in remaining )
						if ( Touching( diamonds[group[head]], diamonds[index] ) ) attached.Add( index );
					foreach ( int index in attached ) { remaining.Remove( index ); group.Add( index ); }
				}
				group.Sort();
				result.Add( group );
			}
		}
		return result;
	}

	/// <summary>
	/// Prefer moving complete assemblies, even across different colors. If an assembly
	/// is blocked, its movable color chunks may peel away. Same-color side bonds never
	/// split, and all members of a chosen assembly share one animation clock.
	/// </summary>
	public static List<SettlementMove> PlanSettlement( IReadOnlyList<Diamond> source, Random random, int incomingStart = -1,
		IReadOnlyList<IReadOnlyList<int>> frozenBonds = null, bool fillCornerPockets = true )
	{
#if STANDALONE
#endif
		var diamonds = new List<Diamond>( source );
		var moves = new List<SettlementMove>();
		var directions = new int[diamonds.Count];
		// Preserve existing bonds and the incoming piece's internal color chunks.
		// New side contacts only bond after this entire settling pass has completed.
		var groups = new List<List<int>>();
		if ( frozenBonds is null ) groups = FindGroups( diamonds, incomingStart );
		else foreach ( var group in frozenBonds ) groups.Add( new List<int>( group ) );
		var workspace = new SettlementWorkspace( diamonds.Count, groups, fillCornerPockets );
		var candidates = new List<MotionCandidate>();
		while ( true )
		{
			workspace.IndexLanes( diamonds );
			candidates.Clear();
			FindMovableAssemblies( diamonds, groups, 0, workspace, candidates );
			FindMovableAssemblies( diamonds, groups, -1, workspace, candidates );
			FindMovableAssemblies( diamonds, groups, 1, workspace, candidates );
			if ( candidates.Count == 0 ) return moves;

			// Prefer the largest coherent assembly over any of its smaller chunks,
			// including when the whole can slide but a smaller part could fall alone.
			candidates.Sort( (a, b) =>
			{
				int order = b.Members.Count.CompareTo( a.Members.Count );
				if ( order != 0 ) return order;
				order = b.Bottom.CompareTo( a.Bottom );
				if ( order != 0 ) return order;
				for ( int i = 0; i < a.Members.Count; i++ )
				{
					order = a.Members[i].CompareTo( b.Members[i] );
					if ( order != 0 ) return order;
				}
				return Math.Abs( a.Direction ).CompareTo( Math.Abs( b.Direction ) );
			} );
			var chosen = candidates[0];
			int directionChosen = chosen.Direction;
			if ( directionChosen != 0 )
			{
				bool bothDirections = candidates.Exists( c => c.Direction == -directionChosen && SameMembers( c.Members, chosen.Members ) );
				if ( bothDirections )
				{
					directionChosen = 0;
					foreach ( int i in chosen.Members ) if ( directions[i] != 0 ) { directionChosen = directions[i]; break; }
					if ( directionChosen == 0 ) directionChosen = random.Next( 2 ) == 0 ? -1 : 1;
				}
			}
			float drop = directionChosen == 0 ? FallDistance( diamonds, chosen.Members, fillCornerPockets, workspace ) : Height * 0.5f;
			var cells = new List<CellMove>( chosen.Members.Count );
			foreach ( int i in chosen.Members )
			{
				var before = diamonds[i];
				diamonds[i] = before with { Lane = before.Lane + directionChosen, Y = before.Y + drop };
				cells.Add( new( i, before, diamonds[i] ) );
				if ( directionChosen != 0 ) directions[i] = directionChosen;
			}
			AppendContinuousMove( moves, new( cells ) );
			// Rebuild temporary movement assemblies, but do not create new color bonds yet.
		}
	}

	static void AppendContinuousMove( List<SettlementMove> moves, SettlementMove next )
	{
		if ( moves.Count > 0 && next.IsSlide )
		{
			var previous = moves[moves.Count - 1];
			bool continues = previous.IsSlide && previous.Cells.Count == next.Cells.Count &&
				Math.Sign( previous.Cells[0].To.Lane - previous.Cells[0].From.Lane ) ==
				Math.Sign( next.Cells[0].To.Lane - next.Cells[0].From.Lane );
			for ( int i = 0; continues && i < next.Cells.Count; i++ )
				continues = previous.Cells[i].Index == next.Cells[i].Index && previous.Cells[i].To == next.Cells[i].From;
			if ( continues )
			{
				var cells = new List<CellMove>( next.Cells.Count );
				for ( int i = 0; i < next.Cells.Count; i++ )
					cells.Add( new( next.Cells[i].Index, previous.Cells[i].From, next.Cells[i].To ) );
				moves[moves.Count - 1] = new( cells );
				return;
			}
		}
		moves.Add( next );
	}

	sealed record MotionCandidate( List<int> Members, int Direction, float Bottom );

	static bool SameMembers( List<int> a, List<int> b )
	{
		if ( a.Count != b.Count ) return false;
		for ( int i = 0; i < a.Count; i++ ) if ( a[i] != b[i] ) return false;
		return true;
	}

	/// <summary>
	/// Scratch storage belongs to one plan: reuse it between directions and steps,
	/// but never retain mutable board state between plans or across boards.
	/// </summary>
	sealed class SettlementWorkspace
	{
		public readonly int[] Owner, Next, Assembly;
		public readonly int[] Heads = new int[LaneCount];
		public readonly bool[] Blocked, Visited, Moving;
		// Mask 1 = touching, mask 2 = movement requires the other group.
		public readonly byte[] Relations;
		public readonly Diamond[] Boundary;

		public SettlementWorkspace( int cells, List<List<int>> groups, bool fillCornerPockets )
		{
			Owner = new int[cells]; Next = new int[cells]; Moving = new bool[cells];
			Assembly = new int[groups.Count]; Blocked = new bool[groups.Count]; Visited = new bool[groups.Count];
			Relations = new byte[groups.Count * groups.Count];
			Boundary = BoundaryDiamonds( fillCornerPockets ).ToArray();
			for ( int group = 0; group < groups.Count; group++ )
				foreach ( int i in groups[group] ) Owner[i] = group;
		}

		public static int Bin( float lane ) => Math.Clamp( (int)MathF.Floor( lane ), 0, LaneCount - 1 );

		public void IndexLanes( List<Diamond> diamonds )
		{
			Array.Fill( Heads, -1 );
			for ( int i = diamonds.Count - 1; i >= 0; i-- )
			{
				int bin = Bin( diamonds[i].Lane );
				Next[i] = Heads[bin]; Heads[bin] = i;
			}
		}

		public bool ClearsBoundary( Diamond cell, int direction, float drop )
		{
			// All wall/corner centers lie at -1, 0, LaneCount-1 or LaneCount.
			// A full path at least two lanes away cannot overlap any of them.
			if ( MathF.Min( cell.Lane, cell.Lane + direction ) >= 2 &&
				MathF.Max( cell.Lane, cell.Lane + direction ) <= LaneCount - 3 ) return true;
			foreach ( var tooth in Boundary )
			{
				if ( MathF.Abs( cell.Lane - tooth.Lane ) * 0.5f + MathF.Abs( cell.Y - tooth.Y ) / Height < 1 - Epsilon / Height ||
					!PathIsClear( cell, tooth, direction, drop ) ) return false;
			}
			return true;
		}
	}

	/// <summary>Eliminate blocked chunks, then join the remaining touching chunks and
	/// movement dependencies. A whole piece can slide away from fixed supports.</summary>
	static void FindMovableAssemblies( List<Diamond> diamonds, List<List<int>> groups, int direction,
		SettlementWorkspace workspace, List<MotionCandidate> result )
	{
		int count = groups.Count;
		var owner = workspace.Owner;
		var blocked = workspace.Blocked;
		var relations = workspace.Relations;
		Array.Clear( blocked ); Array.Clear( relations ); Array.Clear( workspace.Visited );
		// Probe the next rest position; vertical assemblies then travel their full clear distance.
		float drop = Height * 0.5f;
		for ( int i = 0; i < diamonds.Count; i++ )
		{
			var cell = diamonds[i];
			int group = owner[i], row = group * count;
			float lane = cell.Lane + direction;
			if ( lane < 0 || lane >= LaneCount || cell.Y + drop > FloorY( lane ) + Epsilon ) blocked[group] = true;
			if ( !workspace.ClearsBoundary( cell, direction, drop ) ) blocked[group] = true;
			// Conservative swept bounds, including fractional lane positions. Exact diamond
			// tests below retain the original epsilon and corner/face contact semantics.
			int first = SettlementWorkspace.Bin( MathF.Min( cell.Lane, lane ) - 2 );
			int last = SettlementWorkspace.Bin( MathF.Max( cell.Lane, lane ) + 2 );
			for ( int bin = first; bin <= last; bin++ )
			for ( int j = workspace.Heads[bin]; j >= 0; j = workspace.Next[j] )
			{
				int otherGroup = owner[j];
				if ( group == otherGroup ) continue;
				var other = diamonds[j];
				if ( other.Y < cell.Y - Height || other.Y > cell.Y + drop + Height ) continue;
				if ( Touching( cell, other ) ) relations[row + otherGroup] |= 1;
				if ( !PathIsClear( cell, other, direction, drop ) ) relations[row + otherGroup] |= 2;
			}
		}
		bool changed;
		do
		{
			changed = false;
			for ( int group = 0; group < count; group++ )
			{
				if ( blocked[group] ) continue;
				int row = group * count;
				for ( int other = 0; other < count; other++ )
					if ( (relations[row + other] & 2) != 0 && blocked[other] )
					{
						blocked[group] = true; changed = true; break;
					}
			}
		} while ( changed );

		var visited = workspace.Visited;
		var assembly = workspace.Assembly;
		for ( int start = 0; start < count; start++ )
		{
			if ( blocked[start] || visited[start] ) continue;
			assembly[0] = start;
			int assemblyCount = 1;
			var members = new List<int>();
			visited[start] = true;
			float bottom = float.MinValue;
			for ( int head = 0; head < assemblyCount; head++ )
			{
				int group = assembly[head], row = group * count;
				foreach ( int i in groups[group] )
				{
					members.Add( i ); bottom = MathF.Max( bottom, diamonds[i].Y );
				}
				for ( int other = 0; other < count; other++ )
				{
					if ( visited[other] || blocked[other] ) continue;
					if ( relations[row + other] == 0 && (relations[other * count + group] & 2) == 0 ) continue;
					visited[other] = true; assembly[assemblyCount++] = other;
				}
			}
			members.Sort();
			result.Add( new( members, direction, bottom ) );
		}
	}

	static float FallDistance( List<Diamond> diamonds, List<int> members, bool fillCornerPockets, SettlementWorkspace workspace )
	{
		var moving = workspace.Moving;
		Array.Clear( moving );
		foreach ( int i in members ) moving[i] = true;
		float drop = float.MaxValue;
		foreach ( int i in members )
		{
			var cell = diamonds[i];
			float landing = BoundaryLandingY( cell.Lane, cell.Y, fillCornerPockets );
			int last = SettlementWorkspace.Bin( cell.Lane + 2 );
			for ( int bin = SettlementWorkspace.Bin( cell.Lane - 2 ); bin <= last; bin++ )
			for ( int j = workspace.Heads[bin]; j >= 0; j = workspace.Next[j] )
			{
				if ( moving[j] ) continue;
				float dx = MathF.Abs( cell.Lane - diamonds[j].Lane ) * 0.5f;
				if ( dx >= 1 ) continue;
				float contact = diamonds[j].Y - Height * (1 - dx);
				if ( contact >= cell.Y - Epsilon ) landing = MathF.Min( landing, contact );
			}
			drop = MathF.Min( drop, landing - cell.Y );
		}
		return drop;
	}

	static bool PathIsClear( Diamond cell, Diamond other, int direction, float drop )
	{
		float crossX = direction == 0 ? 0 : Math.Clamp( (other.Lane - cell.Lane) / direction, 0, 1 );
		float crossY = Math.Clamp( (other.Y - cell.Y) / drop, 0, 1 );
		return ClearAt( 1 ) && ClearAt( crossX ) && ClearAt( crossY );
		bool ClearAt( float t ) => MathF.Abs( cell.Lane + direction * t - other.Lane ) * 0.5f
			+ MathF.Abs( cell.Y + drop * t - other.Y ) / Height >= 1 - Epsilon / Height;
	}
}