/*
 * ExactNonlinearTreePatternAutomaton.cpp
 *
 *  Created on: 7. 4. 2015
 *      Author: Jan Travnicek
 */

#include "ExactNonlinearTreePatternAutomaton.h"
#include <tree/Tree.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <automaton/Automaton.h>
#include <automaton/PDA/InputDrivenNPDA.h>

#include <tree/properties/ExactSubtreeRepeatsNaive.h>

#include <deque>
#include <alphabet/RankedSymbol.h>

namespace arbology {

namespace exact {

automaton::Automaton ExactNonlinearTreePatternAutomaton::construct ( const tree::Tree & tree, const DefaultSymbolType & subtreeWildcard, const std::set < DefaultSymbolType > & nonlinearVariables ) {
	return dispatch ( tree.getData ( ), subtreeWildcard, nonlinearVariables );
}

void ExactNonlinearTreePatternAutomaton::constructTail ( automaton::InputDrivenNPDA < > & res, const tree::PrefixRankedTree < > & tree, const DefaultSymbolType & subtreeWildcard, const DefaultSymbolType & currentNonlinearVariable, const std::set < DefaultSymbolType > & nonlinearVariables, const std::ranked_symbol < > & subtreeSettings, unsigned subtreeId, std::vector < std::ranked_symbol < > >::const_iterator rankedSymbolsIter, int i, std::vector < std::ranked_symbol < > >::const_iterator subtreeRepeatsIter ) {
	std::deque < std::pair < size_t, int > > subtreeJumps;
	std::deque < std::ranked_symbol < > > subtreeRepeatsStack;

	for (++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i; rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i ) {
		DefaultSymbolType symbol ( alphabet::RankedSymbol < > { * rankedSymbolsIter } );
		subtreeJumps.push_back ( std::make_pair ( ( size_t ) rankedSymbolsIter->getRank ( ), i - 1 ) );
		subtreeRepeatsStack.push_back ( * subtreeRepeatsIter );

		DefaultStateType currentState = DefaultStateType ( i, subtreeId );
		DefaultStateType previousState = DefaultStateType ( i - 1, subtreeId );

		res.addState ( currentState );

		res.addTransition ( previousState, symbol, currentState );

		while ( subtreeJumps.size ( ) && subtreeJumps.back ( ).first == 0 ) {
			DefaultStateType jumpSource = DefaultStateType ( subtreeJumps.back ( ).second, subtreeId );
			res.addTransition ( jumpSource, subtreeWildcard, currentState );

			for ( const DefaultSymbolType & nonlinearVariable : nonlinearVariables )
				if ( nonlinearVariable != currentNonlinearVariable || subtreeSettings == subtreeRepeatsStack.back ( ) )
					res.addTransition ( jumpSource, nonlinearVariable, currentState );

			if ( subtreeJumps.size ( ) ) {
				subtreeJumps.pop_back ( );
				subtreeRepeatsStack.pop_back ( );
			}
		}

		if ( subtreeJumps.size ( ) ) subtreeJumps.back ( ).first--;
	}
}

automaton::InputDrivenNPDA < > ExactNonlinearTreePatternAutomaton::constructInternal ( const tree::PrefixRankedTree < > & tree, const DefaultSymbolType & subtreeWildcard, const DefaultSymbolType & currentNonlinearVariable, const std::set < DefaultSymbolType > & nonlinearVariables ) {
	DefaultSymbolType S = DefaultSymbolType ( 'S' );
	automaton::InputDrivenNPDA < > res ( DefaultStateType ( 0 ), S );

	tree::PrefixRankedTree < > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( tree );
	std::map < DefaultSymbolType, unsigned > repeatsToIds;
	int maxId = 0;

	for ( const std::ranked_symbol < > & repeat : repeats.getContent ( ) )
		if ( !repeatsToIds.count ( repeat.getSymbol ( ) ) )
			repeatsToIds.insert ( std::make_pair ( repeat.getSymbol ( ), maxId++ ) );

	for ( const std::ranked_symbol < > & rankedSymbol : tree.getAlphabet ( ) ) {
		DefaultSymbolType symbol ( alphabet::RankedSymbol < > { rankedSymbol } );
		res.addInputSymbol ( symbol );
		res.setPushdownStoreOperation ( symbol, std::vector < DefaultSymbolType > ( 1, S ), std::vector < DefaultSymbolType > ( ( size_t ) rankedSymbol.getRank ( ), S ) );
	}

	res.addInputSymbol ( subtreeWildcard );
	res.setPushdownStoreOperation ( subtreeWildcard, std::vector < DefaultSymbolType > ( 1, S ), std::vector < DefaultSymbolType > { } );

	for ( const DefaultSymbolType & nonlinearVariable : nonlinearVariables ) {
		res.addInputSymbol ( nonlinearVariable );
		res.setPushdownStoreOperation ( nonlinearVariable, std::vector < DefaultSymbolType > ( 1, S ), std::vector < DefaultSymbolType > { } );
	}

	int i = 1;
	std::deque < std::pair < size_t, int > > subtreeJumps;
	std::deque < std::ranked_symbol < > > subtreeRepeatsStack;

	std::vector < std::ranked_symbol < > >::const_iterator rankedSymbolsIter;
	std::vector < std::ranked_symbol < > >::const_iterator subtreeRepeatsIter;
	for ( rankedSymbolsIter = tree.getContent ( ).begin(), subtreeRepeatsIter = repeats.getContent ( ).begin ( ); rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++ i ) {
		DefaultSymbolType symbol ( alphabet::RankedSymbol < > { * rankedSymbolsIter } );
		subtreeJumps.push_back ( std::make_pair ( ( size_t ) rankedSymbolsIter->getRank ( ), i - 1 ) );
		subtreeRepeatsStack.push_back ( * subtreeRepeatsIter );

		DefaultStateType currentState = DefaultStateType ( i );
		DefaultStateType previousState = DefaultStateType ( i - 1 );

		res.addState ( currentState );

		res.addTransition ( previousState, symbol, currentState );
		res.addTransition ( res.getInitialState ( ), std::move ( symbol ), currentState );

		while ( subtreeJumps.size ( ) && subtreeJumps.back ( ).first == 0 ) {
			DefaultStateType jumpSource = DefaultStateType ( subtreeJumps.back ( ).second );
			res.addTransition ( jumpSource, subtreeWildcard, currentState );

			for ( const DefaultSymbolType & nonlinearVariable : nonlinearVariables )
				if ( nonlinearVariable != currentNonlinearVariable )
					res.addTransition ( jumpSource, nonlinearVariable, currentState );
				else {
					std::ranked_symbol < > subtreeSettings = subtreeRepeatsStack.back ( );
					unsigned subtreeId = repeatsToIds.find ( subtreeSettings.getSymbol ( ) )->second;
					DefaultStateType targetState = DefaultStateType ( i, subtreeId );

					res.addState ( targetState );
					res.addTransition ( jumpSource, nonlinearVariable, targetState );

					constructTail ( res, tree, subtreeWildcard, currentNonlinearVariable, nonlinearVariables, subtreeSettings, subtreeId, rankedSymbolsIter, i, subtreeRepeatsIter );
				}

			subtreeJumps.pop_back ( );
			subtreeRepeatsStack.pop_back ( );
		}

		if ( subtreeJumps.size ( ) ) subtreeJumps.back ( ).first--;
	}

	return res;
}

automaton::InputDrivenNPDA < > ExactNonlinearTreePatternAutomaton::construct ( const tree::PrefixRankedTree < > & tree, const DefaultSymbolType & subtreeWildcard, const std::set < DefaultSymbolType > & nonlinearVariables ) {
	return constructInternal ( tree, subtreeWildcard, * nonlinearVariables.begin ( ), nonlinearVariables );
}

auto ExactNonlinearTreePatternAutomatonPrefixRankedTree = ExactNonlinearTreePatternAutomaton::RegistratorWrapper < automaton::InputDrivenNPDA < >, tree::PrefixRankedTree < > > ( ExactNonlinearTreePatternAutomaton::construct );

} /* namespace exact */

} /* namespace arbology */