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

#ifndef _EXACT_NONLINEAR_TREE_PATTERN_AUTOMATON_H__
#define _EXACT_NONLINEAR_TREE_PATTERN_AUTOMATON_H__

#include <alib/pair>
#include <alib/deque>
#include <alib/vector>

#include <common/ranked_symbol.hpp>

#include <tree/ranked/PrefixRankedTree.h>
#include <automaton/PDA/InputDrivenNPDA.h>

#include <tree/properties/ExactSubtreeRepeatsNaive.h>

namespace arbology {

namespace exact {

class ExactNonlinearTreePatternAutomaton {
	template < class SymbolType, class RankType >
	static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > constructInternal ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables );

	template < class SymbolType, class RankType >
	static void constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables, unsigned subtreeId, typename ext::vector < common::ranked_symbol < SymbolType, RankType > >::const_iterator rankedSymbolsIter, int i, typename ext::vector < common::ranked_symbol < unsigned, RankType > >::const_iterator subtreeRepeatsIter );

public:
	/**
	 * Performs conversion.
	 * @return left regular grammar equivalent to source automaton.
	 */
	template < class SymbolType, class RankType >
	static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > construct ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables );
};

template < class SymbolType, class RankType >
void ExactNonlinearTreePatternAutomaton::constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables, unsigned subtreeId, typename ext::vector < common::ranked_symbol < SymbolType, RankType > >::const_iterator rankedSymbolsIter, int i, typename ext::vector < common::ranked_symbol < unsigned, RankType > >::const_iterator subtreeRepeatsIter ) {
	ext::deque < std::pair < size_t, int > > subtreeJumps;
	ext::deque < unsigned > subtreeRepeatsStack;

	for (++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i; rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i ) {
		common::ranked_symbol < SymbolType, RankType > symbol = * rankedSymbolsIter;
		subtreeJumps.push_back ( std::make_pair ( ( size_t ) symbol.getRank ( ), i - 1 ) );
		subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );

		ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, subtreeId + 1 );
		ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, subtreeId + 1 );

		res.addState ( currentState );

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

		while ( subtreeJumps.size ( ) && subtreeJumps.back ( ).first == 0 ) {
			ext::pair < unsigned, unsigned > jumpSource = ext::make_pair ( subtreeJumps.back ( ).second, subtreeId + 1 );
			res.addTransition ( jumpSource, subtreeWildcard, currentState );

			for ( const common::ranked_symbol < SymbolType, RankType > & nonlinearVariable : nonlinearVariables )
				if ( nonlinearVariable != currentNonlinearVariable || subtreeId == subtreeRepeatsStack.back ( ) )
					res.addTransition ( jumpSource, nonlinearVariable, currentState );

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

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

template < class SymbolType, class RankType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::constructInternal ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables ) {
	char S = alphabet::SubtreeWildcardSymbol::instance < char > ( );
	automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > res ( ext::make_pair ( 0u, 0u ), S );

	tree::PrefixRankedTree < unsigned, DefaultRankType > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( tree );

	for ( const common::ranked_symbol < > & symbol : tree.getAlphabet ( ) ) {
		res.addInputSymbol ( symbol );
		res.setPushdownStoreOperation ( symbol, ext::vector < char > ( 1, S ), ext::vector < char > ( ( size_t ) symbol.getRank ( ), S ) );
	}

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

	for ( const common::ranked_symbol < SymbolType, RankType > & nonlinearVariable : nonlinearVariables ) {
		res.addInputSymbol ( nonlinearVariable );
		res.setPushdownStoreOperation ( nonlinearVariable, ext::vector < char > ( 1, S ), ext::vector < char > { } );
	}

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

	ext::vector < common::ranked_symbol < > >::const_iterator rankedSymbolsIter;
	ext::vector < common::ranked_symbol < unsigned, DefaultRankType > >::const_iterator subtreeRepeatsIter;
	for ( rankedSymbolsIter = tree.getContent ( ).begin(), subtreeRepeatsIter = repeats.getContent ( ).begin ( ); rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++ i ) {
		common::ranked_symbol < SymbolType, RankType > symbol = * rankedSymbolsIter;
		subtreeJumps.push_back ( std::make_pair ( ( size_t ) symbol.getRank ( ), i - 1 ) );
		subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );

		ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, 0u );
		ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, 0u );

		res.addState ( currentState );

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

		while ( subtreeJumps.size ( ) && subtreeJumps.back ( ).first == 0 ) {
			ext::pair < unsigned, unsigned > jumpSource = ext::make_pair ( subtreeJumps.back ( ).second, 0u );
			res.addTransition ( jumpSource, subtreeWildcard, currentState );

			for ( const common::ranked_symbol < SymbolType, RankType > & nonlinearVariable : nonlinearVariables )
				if ( nonlinearVariable != currentNonlinearVariable )
					res.addTransition ( jumpSource, nonlinearVariable, currentState );
				else {
					unsigned subtreeId = subtreeRepeatsStack.back ( );
					ext::pair < unsigned, unsigned > targetState = ext::make_pair ( i, subtreeId + 1 );

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

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

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

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

	return res;
}

template < class SymbolType, class RankType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::construct ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables ) {
	return constructInternal ( tree, subtreeWildcard, * nonlinearVariables.begin ( ), nonlinearVariables );
}

} /* namespace exact */

} /* namespace arbology */

#endif /* _EXACT_NONLINEAR_TREE_PATTERN_AUTOMATON_H__ */