/*
 * TrimFSM.cpp
 *
 *  Created on: 23. 3. 2014
 *	  Author: Tomas Pecka
 */

#include "TrimFSM.h"

#include <exception/AlibException.h>
#include <automaton/FSM/ExtendedNFA.h>
#include <automaton/FSM/CompactNFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>

#include "../../automaton/AutomatonPropertiesFSM.h"

namespace trim {

template<class T>
T TrimFSM::removeUselessStates( const T & fsm ) {
	// 1.
	std::set<automaton::State> Qu = automaton::AutomatonPropertiesFSM::getUsefullStates( fsm );

	// 2.
	T M;

	for( const auto & q : Qu )
		M.addState( q );

	for( const auto & a : fsm.getInputAlphabet( ) )
		M.addInputSymbol( a );

	for( const auto & t : fsm.getTransitions( ) )
		for( const auto & to : t.second )
			if( /* TODO test this Qu.count(t.first.first) ) && */ Qu.count(to) )
				M.addTransition( t.first.first, t.first.second, to );

	for( const auto & q : fsm.getInitialStates( ) )
		M.addInitialState( q );

	for( const auto & q : fsm.getFinalStates( ) )
		M.addFinalState( q );

	return M;
}

template automaton::EpsilonNFA TrimFSM::removeUselessStates( const automaton::EpsilonNFA & fsm );
template automaton::NFA TrimFSM::removeUselessStates( const automaton::NFA & fsm );
template automaton::CompactNFA TrimFSM::removeUselessStates( const automaton::CompactNFA & fsm );
template automaton::ExtendedNFA TrimFSM::removeUselessStates( const automaton::ExtendedNFA & fsm );

template<>
automaton::DFA TrimFSM::removeUselessStates( const automaton::DFA & fsm ) {
	// 1.
	std::set<automaton::State> Qu = automaton::AutomatonPropertiesFSM::getUsefullStates( fsm );

	// 2.
	automaton::DFA M ( fsm.getInitialState () );

	for( const auto & q : Qu )
		M.addState( q );

	for( const auto & a : fsm.getInputAlphabet( ) )
		M.addInputSymbol( a );

	for( const auto & t : fsm.getTransitions( ) )
		if( /* TODO test this Qu.count( t.first.first ) && */ Qu.count( t.second ) )
			M.addTransition( t.first.first, t.first.second, t.second );

	for( const auto & q : fsm.getFinalStates( ) )
		M.addFinalState( q );

	return M;
}

template<class T>
T TrimFSM::removeUnreachableStates( const T & fsm ) {
	// 1a
	std::set<automaton::State> Qa = automaton::AutomatonPropertiesFSM::getUnreachableStates( fsm );

	// 2
	T M;

	for( const auto & q : Qa )
		M.addState( q );

	for( const auto & a : fsm.getInputAlphabet( ) )
		M.addInputSymbol( a );

	for( const auto & transition : fsm.getTransitions( ) )
		if( Qa.count( transition.first.first ) )
			for(const auto& to : transition.second )
				M.addTransition( transition.first.first, transition.first.second, to );

	for( const auto & q : fsm.getInitialStates( ) )
		M.addInitialState( q );

	std::set<automaton::State> intersect;
	std::set_intersection( fsm.getFinalStates( ).begin(), fsm.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( intersect, intersect.begin( ) ) );
	for( auto const & state : intersect )
		M.addFinalState( state );

	return M;
}

template automaton::EpsilonNFA TrimFSM::removeUnreachableStates( const automaton::EpsilonNFA & fsm );
template automaton::NFA TrimFSM::removeUnreachableStates( const automaton::NFA & fsm );
template automaton::CompactNFA TrimFSM::removeUnreachableStates( const automaton::CompactNFA & fsm );
template automaton::ExtendedNFA TrimFSM::removeUnreachableStates( const automaton::ExtendedNFA & fsm );

template<>
automaton::DFA TrimFSM::removeUnreachableStates( const automaton::DFA & fsm ) {
	// 1a
	std::set<automaton::State> Qa = automaton::AutomatonPropertiesFSM::getUnreachableStates( fsm );

	// 2
	automaton::DFA M(fsm.getInitialState() );

	for( const auto & q : Qa )
		M.addState( q );

	for( const auto & a : fsm.getInputAlphabet( ) )
		M.addInputSymbol( a );

	for( const auto & transition : fsm.getTransitions( ) )
		if( Qa.count( transition.first.first ) )
			M.addTransition( transition.first.first, transition.first.second, transition.second );

	std::set<automaton::State> intersect;
	std::set_intersection( fsm.getFinalStates( ).begin(), fsm.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( intersect, intersect.begin( ) ) );
	for( auto const & state : intersect )
		M.addFinalState( state );

	return M;
}

template<class T>
T TrimFSM::trim( const T & fsm ) {
	return removeUnreachableStates(removeUselessStates(fsm));
}

template automaton::EpsilonNFA TrimFSM::trim( const automaton::EpsilonNFA & fsm );
template automaton::NFA TrimFSM::trim( const automaton::NFA & fsm );
template automaton::CompactNFA TrimFSM::trim( const automaton::CompactNFA & fsm );
template automaton::ExtendedNFA TrimFSM::trim( const automaton::ExtendedNFA & fsm );
template automaton::DFA TrimFSM::trim( const automaton::DFA & fsm );

}