ExactPatternMatchingAutomaton.cpp

/*
 * ExactPatternMatchingAutomaton.cpp
 *
 *  Created on: 9. 2. 2014
 *      Author: Jan Travnicek
 */

#include "ExactPatternMatchingAutomaton.h"
#include "ExactSubtreeMatchingAutomaton.h"
#include "SubtreeJumpTable.h"

#include <tree/ranked/RankedTree.h>
#include <tree/ranked/RankedPattern.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedBarPattern.h>

#include <automaton/PDA/InputDrivenNPDA.h>
#include <automaton/PDA/VisiblyPushdownNPDA.h>
#include <automaton/PDA/NPDA.h>
#include <automaton/TA/NFTA.h>

#include <alphabet/BottomOfTheStackSymbol.h>

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

namespace arbology {

namespace exact {

automaton::Automaton ExactPatternMatchingAutomaton::construct ( const tree::Tree & pattern ) {
	return dispatch ( pattern.getData ( ) );
}

automaton::InputDrivenNPDA < > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedTree < > & pattern ) {
	return ExactSubtreeMatchingAutomaton::construct ( pattern );
}

auto ExactPatternMatchingAutomatonPrefixRankedTree = ExactPatternMatchingAutomaton::RegistratorWrapper < automaton::InputDrivenNPDA < >, tree::PrefixRankedTree < > > ( ExactPatternMatchingAutomaton::construct );

std::vector < alphabet::Symbol > computeRHS ( const tree::PrefixRankedPattern < > & pattern, const std::vector < int > & patternSubtreeJumpTable, int i ) {
	const std::vector < std::ranked_symbol < > > & content = pattern.getContent ( );

	unsigned rank = content[i].getRank ( ).getData ( );

	i++;

	std::vector < alphabet::Symbol > res;

	for ( unsigned ranki = 0; ranki < rank; ranki++ ) {
		if ( content[i] == pattern.getSubtreeWildcard ( ) ) {
			res.push_back ( alphabet::symbolFrom ( 'R' ) );
			i++;
		} else {
			res.push_back ( alphabet::symbolFrom ( 'T' ) );

			i = patternSubtreeJumpTable[i];
		}
	}

	return res;
}

automaton::NPDA < > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedPattern < > & pattern ) {
	automaton::NPDA < > res ( label::labelFrom ( 0 ), alphabet::symbolFrom ( 'T' ) );

	for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		if ( symbol == pattern.getSubtreeWildcard ( ) ) continue;

		res.addInputSymbol ( alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ) );
	}

	res.setPushdownStoreAlphabet ( { alphabet::symbolFrom ( 'T' ), alphabet::symbolFrom ( 'R' ) } );

	for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		if ( symbol == pattern.getSubtreeWildcard ( ) ) continue;

		res.addTransition ( label::labelFrom ( 0 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), std::vector < alphabet::Symbol > ( 1, alphabet::symbolFrom ( 'T' ) ), label::labelFrom ( 0 ), std::vector < alphabet::Symbol > ( symbol.getRank ( ).getData ( ), alphabet::symbolFrom ( 'T' ) ) );
	}

	std::vector < int > patternSubtreeJumpTable = SubtreeJumpTable::compute ( pattern );

	int i = 1;

	for ( const std::ranked_symbol < > & symbol : pattern.getContent ( ) ) {
		res.addState ( label::labelFrom ( i ) );

		if ( symbol == pattern.getSubtreeWildcard ( ) )
			for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
				if ( symbol == pattern.getSubtreeWildcard ( ) ) continue;

				if ( symbol.getRank ( ).getData ( ) == 0 ) {
					res.addTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), std::vector < alphabet::Symbol > ( 1, alphabet::symbolFrom ( 'T' ) ), label::labelFrom ( i - 1 ), std::vector < alphabet::Symbol > { } );

					res.addTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), std::vector < alphabet::Symbol > ( 1, alphabet::symbolFrom ( 'R' ) ), label::labelFrom ( i ), std::vector < alphabet::Symbol > { } );
				} else {
					std::vector < alphabet::Symbol > push ( symbol.getRank ( ).getData ( ), alphabet::symbolFrom ( 'T' ) );
					res.addTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), std::vector < alphabet::Symbol > ( 1, alphabet::symbolFrom ( 'T' ) ), label::labelFrom ( i - 1 ), push );

					push[symbol.getRank ( ).getData ( ) - 1] = alphabet::symbolFrom ( 'R' );
					res.addTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), std::vector < alphabet::Symbol > ( 1, alphabet::symbolFrom ( 'R' ) ), label::labelFrom ( i - 1 ), push );
				}
			}

		else
			res.addTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), std::vector < alphabet::Symbol > ( 1, alphabet::symbolFrom ( 'T' ) ), label::labelFrom ( i ), computeRHS ( pattern, patternSubtreeJumpTable, i - 1 ) );

		i++;
	}

	res.addFinalState ( label::labelFrom ( i - 1 ) );
	return res;
}

auto ExactPatternMatchingAutomatonPrefixRankedPattern = ExactPatternMatchingAutomaton::RegistratorWrapper < automaton::NPDA < >, tree::PrefixRankedPattern < > > ( ExactPatternMatchingAutomaton::construct );

automaton::InputDrivenNPDA < > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedBarTree < > & pattern ) {
	return ExactSubtreeMatchingAutomaton::construct ( pattern );
}

auto ExactPatternMatchingAutomatonPrefixRankedBarTree = ExactPatternMatchingAutomaton::RegistratorWrapper < automaton::InputDrivenNPDA < >, tree::PrefixRankedBarTree < > > ( ExactPatternMatchingAutomaton::construct );

automaton::VisiblyPushdownNPDA < > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedBarPattern & pattern ) {
	automaton::VisiblyPushdownNPDA < > res ( alphabet::Symbol { alphabet::BottomOfTheStackSymbol::BOTTOM_OF_THE_STACK } );

	res.addState ( label::labelFrom ( 0 ) );
	res.addInitialState ( label::labelFrom ( 0 ) );

	for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;

		if ( pattern.getBars ( ).count ( symbol ) )
			res.addReturnInputSymbol ( alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ) );
		else
			res.addCallInputSymbol ( alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ) );
	}

	res.setPushdownStoreAlphabet ( { alphabet::Symbol { alphabet::BottomOfTheStackSymbol::BOTTOM_OF_THE_STACK }, alphabet::symbolFrom ( 'T' ), alphabet::symbolFrom ( 'R' ) } );

	for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;

		if ( pattern.getBars ( ).count ( symbol ) )
			res.addReturnTransition ( label::labelFrom ( 0 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), alphabet::symbolFrom ( 'T' ), label::labelFrom ( 0 ) );
		else
			res.addCallTransition ( label::labelFrom ( 0 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), label::labelFrom ( 0 ), alphabet::symbolFrom ( 'T' ) );
	}

	int i = 1;

	for ( const std::ranked_symbol < > & symbol : pattern.getContent ( ) ) {
		res.addState ( label::labelFrom ( i ) );

		if ( symbol == pattern.getSubtreeWildcard ( ) ) {
			for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
				if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) || ( pattern.getBars ( ).count ( symbol ) ) ) continue;

				res.addCallTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), label::labelFrom ( i ), alphabet::symbolFrom ( 'R' ) );
			}
		} else if ( symbol == pattern.getVariablesBar ( ) ) {
			for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
				if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;

				if ( pattern.getBars ( ).count ( symbol ) )
					res.addReturnTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), alphabet::symbolFrom ( 'T' ), label::labelFrom ( i - 1 ) );
				else
					res.addCallTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), label::labelFrom ( i - 1 ), alphabet::symbolFrom ( 'T' ) );
			}

			for ( const std::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
				if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) || ( ! pattern.getBars ( ).count ( symbol ) ) ) continue;

				res.addReturnTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), alphabet::symbolFrom ( 'R' ), label::labelFrom ( i ) );
			}
		} else if ( pattern.getBars ( ).count ( symbol ) ) {
			res.addReturnTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), alphabet::symbolFrom ( 'T' ), label::labelFrom ( i ) );
		} else {
			res.addCallTransition ( label::labelFrom ( i - 1 ), alphabet::Symbol ( alphabet::RankedSymbol < > { symbol } ), label::labelFrom ( i ), alphabet::symbolFrom ( 'T' ) );
		}

		i++;
	}

	res.addFinalState ( label::labelFrom ( i - 1 ) );
	return res;
}

auto ExactPatternMatchingAutomatonPrefixRankedBarPattern = ExactPatternMatchingAutomaton::RegistratorWrapper < automaton::VisiblyPushdownNPDA < >, tree::PrefixRankedBarPattern > ( ExactPatternMatchingAutomaton::construct );

automaton::NFTA ExactPatternMatchingAutomaton::construct ( const tree::RankedTree < > & pattern ) {
	return ExactSubtreeMatchingAutomaton::construct ( pattern );
}

auto ExactPatternMatchingAutomatonRankedTree = ExactPatternMatchingAutomaton::RegistratorWrapper < automaton::NFTA, tree::RankedTree < > > ( ExactPatternMatchingAutomaton::construct );

label::Label constructRecursivePattern ( const std::tree < std::ranked_symbol < > > & node, automaton::NFTA & res, const std::ranked_symbol < > & subtreeWildcard, const label::Label & loopState, int & nextState ) {
	if ( node.getData ( ) == subtreeWildcard ) {
		label::Label state = label::labelFrom ( nextState++ );
		res.addState ( state );

		for ( const std::ranked_symbol < > & symbol : res.getInputAlphabet ( ) ) {
			std::vector < label::Label > states;
			states.reserve ( symbol.getRank ( ).getData ( ) );

			for ( unsigned i = 0; i < symbol.getRank ( ).getData ( ); i++ )
				states.push_back ( loopState );

			res.addTransition ( symbol, states, state );
		}

		return state;
	} else {
		std::vector < label::Label > states;
		states.reserve ( node.getData ( ).getRank ( ).getData ( ) );

		for ( const std::tree < std::ranked_symbol < > > & child : node.getChildren ( ) )
			states.push_back ( constructRecursivePattern ( child, res, subtreeWildcard, loopState, nextState ) );

		label::Label state = label::labelFrom ( nextState++ );
		res.addState ( state );
		res.addTransition ( node.getData ( ), states, state );
		return state;
	}
}

automaton::NFTA ExactPatternMatchingAutomaton::construct ( const tree::RankedPattern < > & pattern ) {
	std::set < std::ranked_symbol < > > alphabet = pattern.getAlphabet ( );

	alphabet.erase ( pattern.getSubtreeWildcard ( ) );

	automaton::NFTA res;
	res.setInputAlphabet ( alphabet );

	int nextState = 0;

	label::Label loopState = label::labelFrom ( nextState++ );
	res.addState ( loopState );

	for ( const std::ranked_symbol < > & symbol : res.getInputAlphabet ( ) ) {
		std::vector < label::Label > states;
		states.reserve ( symbol.getRank ( ).getData ( ) );

		for ( unsigned i = 0; i < symbol.getRank ( ).getData ( ); i++ )
			states.push_back ( loopState );

		res.addTransition ( symbol, states, loopState );
	}

	res.addFinalState ( constructRecursivePattern ( pattern.getContent ( ), res, pattern.getSubtreeWildcard ( ), loopState, nextState ) );
	return res;
}

auto ExactPatternMatchingAutomatonRankedPattern = ExactPatternMatchingAutomaton::RegistratorWrapper < automaton::NFTA, tree::RankedPattern < > > ( ExactPatternMatchingAutomaton::construct );

} /* namespace exact */

} /* namespace arbology */