// Clean-room implementation for HyperTwist algorithm-language subsystem
// Implemented from governance docs only (Phase 0R-D, Phase 1R, Phase 5R-A)
// Source: Behavioral contracts from cubing/alg.js Model A handoff (GPL-3.0-or-later lane)
//         No source code inspection. Clean-room workflow only.
// Date: 2026-05-15
// Bound 2 - Traversal and transformation helpers

#include "HyperTwistAlgorithm/HyperTwistAlgorithmTraversal.h"

namespace HyperTwistAlgorithmTraversalInternal
{
	static FHyperTwistAlgorithmBlockMove InvertBlockMove(const FHyperTwistAlgorithmBlockMove& Move)
	{
		FHyperTwistAlgorithmBlockMove Result = Move;
		Result.Amount = -Move.Amount;
		return Result;
	}

	static FHyperTwistAlgorithmNode MakeBlockMoveNode(const FHyperTwistAlgorithmBlockMove& Move)
	{
		FHyperTwistAlgorithmNode Result;
		Result.NodeType = EHyperTwistAlgorithmNodeType::BlockMove;
		Result.BlockMove = Move;
		return Result;
	}

	static TArray<FHyperTwistAlgorithmNode> InvertNodeList(const TArray<FHyperTwistAlgorithmNode>& Nodes);
	static TArray<FHyperTwistAlgorithmNode> CoalesceNodeList(const TArray<FHyperTwistAlgorithmNode>& Nodes);

	static FHyperTwistAlgorithmNode InvertNode(const FHyperTwistAlgorithmNode& Node)
	{
		FHyperTwistAlgorithmNode Result = Node;

		switch (Node.NodeType)
		{
		case EHyperTwistAlgorithmNodeType::BlockMove:
			Result.BlockMove = InvertBlockMove(Node.BlockMove);
			break;

		case EHyperTwistAlgorithmNodeType::Group:
			Result.Group.Inner = InvertNodeList(Node.Group.Inner);
			break;

		case EHyperTwistAlgorithmNodeType::Commutator:
			Result.Commutator.A = Node.Commutator.B;
			Result.Commutator.B = Node.Commutator.A;
			break;

		case EHyperTwistAlgorithmNodeType::Conjugate:
			Result.Conjugate.A = Node.Conjugate.A;
			Result.Conjugate.B = InvertNodeList(Node.Conjugate.B);
			break;

		case EHyperTwistAlgorithmNodeType::Pause:
		case EHyperTwistAlgorithmNodeType::Newline:
		case EHyperTwistAlgorithmNodeType::Comment:
		case EHyperTwistAlgorithmNodeType::Sequence:
		default:
			break;
		}

		return Result;
	}

	static TArray<FHyperTwistAlgorithmNode> InvertNodeList(const TArray<FHyperTwistAlgorithmNode>& Nodes)
	{
		TArray<FHyperTwistAlgorithmNode> Result;
		Result.Reserve(Nodes.Num());

		for (int32 Index = Nodes.Num() - 1; Index >= 0; --Index)
		{
			Result.Add(InvertNode(Nodes[Index]));
		}

		return Result;
	}

	static void AppendRepeatedNodes(
		const TArray<FHyperTwistAlgorithmNode>& Nodes,
		const int32 Amount,
		TArray<FHyperTwistAlgorithmNode>& OutNodes)
	{
		const int32 RepeatCount = FMath::Abs(Amount);
		if (RepeatCount == 0 || Nodes.Num() == 0)
		{
			return;
		}

		if (Amount < 0)
		{
			const TArray<FHyperTwistAlgorithmNode> InvertedNodes = InvertNodeList(Nodes);
			for (int32 RepeatIndex = 0; RepeatIndex < RepeatCount; ++RepeatIndex)
			{
				OutNodes.Append(InvertedNodes);
			}
			return;
		}

		for (int32 RepeatIndex = 0; RepeatIndex < RepeatCount; ++RepeatIndex)
		{
			OutNodes.Append(Nodes);
		}
	}

	static void ExpandNodeListToSequence(
		const TArray<FHyperTwistAlgorithmNode>& Nodes,
		TArray<FHyperTwistAlgorithmNode>& OutNodes);

	static void ExpandNodeToSequence(
		const FHyperTwistAlgorithmNode& Node,
		TArray<FHyperTwistAlgorithmNode>& OutNodes)
	{
		switch (Node.NodeType)
		{
		case EHyperTwistAlgorithmNodeType::BlockMove:
		case EHyperTwistAlgorithmNodeType::Pause:
		case EHyperTwistAlgorithmNodeType::Newline:
		case EHyperTwistAlgorithmNodeType::Comment:
			OutNodes.Add(Node);
			break;

		case EHyperTwistAlgorithmNodeType::Group:
			{
				TArray<FHyperTwistAlgorithmNode> ExpandedInner;
				ExpandNodeListToSequence(Node.Group.Inner, ExpandedInner);
				AppendRepeatedNodes(ExpandedInner, Node.Group.Amount, OutNodes);
			}
			break;

		case EHyperTwistAlgorithmNodeType::Commutator:
			{
				TArray<FHyperTwistAlgorithmNode> ExpandedLeft;
				TArray<FHyperTwistAlgorithmNode> ExpandedRight;
				TArray<FHyperTwistAlgorithmNode> ExpandedNodeRun;
				ExpandNodeListToSequence(Node.Commutator.A, ExpandedLeft);
				ExpandNodeListToSequence(Node.Commutator.B, ExpandedRight);

				ExpandedNodeRun.Append(ExpandedLeft);
				ExpandedNodeRun.Append(ExpandedRight);
				ExpandedNodeRun.Append(InvertNodeList(ExpandedLeft));
				ExpandedNodeRun.Append(InvertNodeList(ExpandedRight));
				AppendRepeatedNodes(ExpandedNodeRun, Node.Commutator.Amount, OutNodes);
			}
			break;

		case EHyperTwistAlgorithmNodeType::Conjugate:
			{
				TArray<FHyperTwistAlgorithmNode> ExpandedLeft;
				TArray<FHyperTwistAlgorithmNode> ExpandedRight;
				TArray<FHyperTwistAlgorithmNode> ExpandedNodeRun;
				ExpandNodeListToSequence(Node.Conjugate.A, ExpandedLeft);
				ExpandNodeListToSequence(Node.Conjugate.B, ExpandedRight);

				ExpandedNodeRun.Append(ExpandedLeft);
				ExpandedNodeRun.Append(ExpandedRight);
				ExpandedNodeRun.Append(InvertNodeList(ExpandedLeft));
				AppendRepeatedNodes(ExpandedNodeRun, Node.Conjugate.Amount, OutNodes);
			}
			break;

		case EHyperTwistAlgorithmNodeType::Sequence:
		default:
			break;
		}
	}

	static void ExpandNodeListToSequence(
		const TArray<FHyperTwistAlgorithmNode>& Nodes,
		TArray<FHyperTwistAlgorithmNode>& OutNodes)
	{
		for (const FHyperTwistAlgorithmNode& Node : Nodes)
		{
			ExpandNodeToSequence(Node, OutNodes);
		}
	}

	static bool MovesAreCoalesceable(
		const FHyperTwistAlgorithmBlockMove& A,
		const FHyperTwistAlgorithmBlockMove& B)
	{
		return A.Family == B.Family
			&& A.UsesWideSuffix() == B.UsesWideSuffix()
			&& A.GetCanonicalMoveType() == B.GetCanonicalMoveType()
			&& A.GetCanonicalInnerLayer() == B.GetCanonicalInnerLayer()
			&& A.GetCanonicalOuterLayer() == B.GetCanonicalOuterLayer();
	}

	static void AppendCoalescedBlockMove(
		TArray<FHyperTwistAlgorithmNode>& OutNodes,
		const FHyperTwistAlgorithmBlockMove& Move)
	{
		if (Move.Amount == 0)
		{
			return;
		}

		if (OutNodes.Num() > 0
			&& OutNodes.Last().NodeType == EHyperTwistAlgorithmNodeType::BlockMove
			&& MovesAreCoalesceable(OutNodes.Last().BlockMove, Move))
		{
			const int32 CombinedAmount = OutNodes.Last().BlockMove.Amount + Move.Amount;
			if (CombinedAmount == 0)
			{
				OutNodes.RemoveAt(OutNodes.Num() - 1);
			}
			else
			{
				OutNodes.Last().BlockMove.Amount = CombinedAmount;
			}
			return;
		}

		OutNodes.Add(MakeBlockMoveNode(Move));
	}

	static FHyperTwistAlgorithmNode CoalesceNode(const FHyperTwistAlgorithmNode& Node)
	{
		FHyperTwistAlgorithmNode Result = Node;

		switch (Node.NodeType)
		{
		case EHyperTwistAlgorithmNodeType::Group:
			Result.Group.Inner = CoalesceNodeList(Node.Group.Inner);
			break;

		case EHyperTwistAlgorithmNodeType::Commutator:
			Result.Commutator.A = CoalesceNodeList(Node.Commutator.A);
			Result.Commutator.B = CoalesceNodeList(Node.Commutator.B);
			break;

		case EHyperTwistAlgorithmNodeType::Conjugate:
			Result.Conjugate.A = CoalesceNodeList(Node.Conjugate.A);
			Result.Conjugate.B = CoalesceNodeList(Node.Conjugate.B);
			break;

		case EHyperTwistAlgorithmNodeType::BlockMove:
		case EHyperTwistAlgorithmNodeType::Pause:
		case EHyperTwistAlgorithmNodeType::Newline:
		case EHyperTwistAlgorithmNodeType::Comment:
		case EHyperTwistAlgorithmNodeType::Sequence:
		default:
			break;
		}

		return Result;
	}

	static TArray<FHyperTwistAlgorithmNode> CoalesceNodeList(const TArray<FHyperTwistAlgorithmNode>& Nodes)
	{
		TArray<FHyperTwistAlgorithmNode> Result;
		Result.Reserve(Nodes.Num());

		for (const FHyperTwistAlgorithmNode& Node : Nodes)
		{
			if (Node.NodeType == EHyperTwistAlgorithmNodeType::BlockMove)
			{
				AppendCoalescedBlockMove(Result, Node.BlockMove);
				continue;
			}

			Result.Add(CoalesceNode(Node));
		}

		return Result;
	}
}

FHyperTwistAlgorithmSequence UHyperTwistAlgorithmTraversal::InvertSequence(
	const FHyperTwistAlgorithmSequence& Sequence)
{
	FHyperTwistAlgorithmSequence Result;
	Result.Nodes = HyperTwistAlgorithmTraversalInternal::InvertNodeList(Sequence.Nodes);
	return Result;
}

FHyperTwistAlgorithmSequence UHyperTwistAlgorithmTraversal::ExpandToFlatSequence(
	const FHyperTwistAlgorithmSequence& Sequence)
{
	FHyperTwistAlgorithmSequence Result;
	HyperTwistAlgorithmTraversalInternal::ExpandNodeListToSequence(Sequence.Nodes, Result.Nodes);
	return Result;
}

TArray<FHyperTwistAlgorithmBlockMove> UHyperTwistAlgorithmTraversal::ExpandToFlatMoves(
	const FHyperTwistAlgorithmSequence& Sequence)
{
	const FHyperTwistAlgorithmSequence ExpandedSequence = ExpandToFlatSequence(Sequence);

	TArray<FHyperTwistAlgorithmBlockMove> Result;
	for (const FHyperTwistAlgorithmNode& Node : ExpandedSequence.Nodes)
	{
		if (Node.NodeType == EHyperTwistAlgorithmNodeType::BlockMove)
		{
			Result.Add(Node.BlockMove);
		}
	}

	return Result;
}

TArray<FHyperTwistAlgorithmBlockMove> UHyperTwistAlgorithmTraversal::CoalesceMoves(
	const TArray<FHyperTwistAlgorithmBlockMove>& Moves)
{
	TArray<FHyperTwistAlgorithmNode> CoalescedNodes;
	CoalescedNodes.Reserve(Moves.Num());

	for (const FHyperTwistAlgorithmBlockMove& Move : Moves)
	{
		HyperTwistAlgorithmTraversalInternal::AppendCoalescedBlockMove(CoalescedNodes, Move);
	}

	TArray<FHyperTwistAlgorithmBlockMove> Result;
	Result.Reserve(CoalescedNodes.Num());
	for (const FHyperTwistAlgorithmNode& Node : CoalescedNodes)
	{
		if (Node.NodeType == EHyperTwistAlgorithmNodeType::BlockMove)
		{
			Result.Add(Node.BlockMove);
		}
	}

	return Result;
}

FHyperTwistAlgorithmSequence UHyperTwistAlgorithmTraversal::CoalesceSequence(
	const FHyperTwistAlgorithmSequence& Sequence)
{
	FHyperTwistAlgorithmSequence Result;
	Result.Nodes = HyperTwistAlgorithmTraversalInternal::CoalesceNodeList(Sequence.Nodes);
	return Result;
}

FHyperTwistAlgorithmSequence UHyperTwistAlgorithmTraversal::ExpandAndCoalesceSequence(
	const FHyperTwistAlgorithmSequence& Sequence)
{
	return CoalesceSequence(ExpandToFlatSequence(Sequence));
}

TArray<FHyperTwistAlgorithmBlockMove> UHyperTwistAlgorithmTraversal::ExpandAndSimplify(
	const FHyperTwistAlgorithmSequence& Sequence)
{
	return CoalesceMoves(ExpandToFlatMoves(Sequence));
}
