#include <catch2/catch.hpp>

#include <alib/list>

#include "automaton/transform/AutomataConcatenation.h"
#include "automaton/transform/AutomataConcatenationEpsilonTransition.h"

#include "automaton/simplify/MinimizeBrzozowski.h"
#include "automaton/simplify/Normalize.h"
#include "automaton/simplify/EpsilonRemoverIncoming.h"
#include "automaton/simplify/Trim.h"
#include "automaton/simplify/Total.h"
#include "automaton/determinize/Determinize.h"

TEST_CASE ( "Automata Concatenation", "[unit][algo][automaton][transform]" ) {
	SECTION ( "NFA/DFA" ) {
		// based on Melichar, 2.79

		DefaultStateType q1a = DefaultStateType("1");
		DefaultStateType q2a = DefaultStateType("2");
		DefaultStateType q0a = DefaultStateType("0");
		DefaultStateType q1b = DefaultStateType("1'");
		DefaultStateType q2b = DefaultStateType("2'");
		DefaultStateType q0b = DefaultStateType("0'");
		DefaultStateType q0102 = DefaultStateType("q0102");
		DefaultSymbolType a(DefaultSymbolType('a')), b(DefaultSymbolType('b'));

		automaton::DFA<> m1(q1a);
		automaton::DFA<> m2(q1b);
		automaton::NFA < >  m3(q1a);

		m1.setInputAlphabet({a, b});
		m1.setStates({q1a, q2a, q0a});
		m1.addTransition(q1a, a, q2a);
		m1.addTransition(q1a, b, q0a);
		m1.addTransition(q2a, a, q2a);
		m1.addTransition(q2a, b, q0a);
		m1.addTransition(q0a, a, q0a);
		m1.addTransition(q0a, b, q0a);
		m1.addFinalState(q2a);

		m2.setInputAlphabet({a, b});
		m2.setStates({q1b, q2b});
		m2.addTransition(q1b, b, q2b);
		m2.addTransition(q2b, b, q2b);
		m2.addFinalState(q2b);

		m3.setInputAlphabet({a, b});
		m3.setStates({q1a, q1b, q2a, q2b, q0a, q0b, q0102});
		m3.addTransition(q1a, a, q2a);
		m3.addTransition(q1a, a, q1b);
		m3.addTransition(q1a, b, q0a);
		m3.addTransition(q2a, a, q2a);
		m3.addTransition(q2a, a, q1b);
		m3.addTransition(q2a, b, q0a);
		m3.addTransition(q0a, a, q0a);
		m3.addTransition(q0a, b, q0a);
		m3.addTransition(q1b, a, q0b);
		m3.addTransition(q1b, b, q2b);
		m3.addTransition(q2b, a, q0b);
		m3.addTransition(q2b, b, q2b);
		m3.addTransition(q0b, a, q0b);
		m3.addTransition(q0b, b, q0b);
		m3.setFinalStates({q2b});

		auto u11 = automaton::transform::AutomataConcatenationEpsilonTransition::concatenation(automaton::NFA<>(m1), automaton::NFA < > (m2));
		auto u12 = automaton::transform::AutomataConcatenationEpsilonTransition::concatenation(m1, m2);
		auto u21 = automaton::transform::AutomataConcatenation::concatenation(automaton::NFA<>(m1), automaton::NFA < > (m2));
		auto u22 = automaton::transform::AutomataConcatenation::concatenation(m1, m2);

		automaton::DFA < DefaultSymbolType, unsigned > umdfa (automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(m3)))));
		automaton::DFA < DefaultSymbolType, unsigned > umdfa11(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u11)))));
		automaton::DFA < DefaultSymbolType, unsigned > umdfa12(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u12)))));
		automaton::DFA < DefaultSymbolType, unsigned > umdfa21(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u21)))));
		automaton::DFA < DefaultSymbolType, unsigned > umdfa22(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u22)))));

		CHECK(umdfa11 == umdfa);
		CHECK(umdfa12 == umdfa);
		CHECK(umdfa21 == umdfa);
		CHECK(umdfa22 == umdfa);
	}

	SECTION ( "No epsilon transitions, first automaton has a word of length 1" ) {
		// Bug in AAG slides and our algorithm

		auto A = DefaultStateType ( "A" );
		auto B = DefaultStateType ( "B" );
		auto C = DefaultStateType ( "C" );
		auto a = DefaultSymbolType ( 'a' );
		auto b = DefaultSymbolType ( 'b' );
		auto init = std::make_pair ( label::InitialStateLabel::instance < DefaultStateType > ( ), 0 );

		automaton::DFA < > m1 ( A );
		m1.setStates ( { A, B } );
		m1.setInputAlphabet ( { a, b } );
		m1.setFinalStates ( { A, B } );
		m1.addTransition ( A, a, B );

		automaton::DFA < > m2 ( C );
		m2.setStates ( { C } );
		m2.setInputAlphabet ( { a, b } );
		m2.setFinalStates ( { C } );
		m2.addTransition ( C, b, C );

		automaton::NFA < DefaultSymbolType, ext::pair < DefaultStateType, unsigned > > expected ( init );
		expected.setStates ( { init, { A, 1 }, { B, 1 }, { C, 2 } } );
		expected.setInputAlphabet ( { a, b } );
		expected.setFinalStates ( { init, { C, 2 } } );
		expected.addTransition ( init, a, { B, 1 } );
		expected.addTransition ( init, a, { C, 2 } );
		expected.addTransition ( init, b, { C, 2 } );
		expected.addTransition ( { A, 1 }, a, { B, 1 } );
		expected.addTransition ( { A, 1 }, a, { C, 2 } );
		expected.addTransition ( { C, 2 }, b, { C, 2 } );


		CHECK ( automaton::transform::AutomataConcatenation::concatenation ( m1, m2 ) == expected );
	}
}