ExactSubtreeMatchingAutomaton.cpp

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

#include "ExactSubtreeMatchingAutomaton.h"
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/RankedTree.h>

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

#include <alphabet/BottomOfTheStackSymbol.h>

#include <deque>

namespace arbology {

namespace exact {

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

automaton::InputDrivenNPDA ExactSubtreeMatchingAutomaton::construct ( const tree::PrefixRankedTree & pattern ) {
	automaton::InputDrivenNPDA res ( automaton::State ( 0 ), alphabet::symbolFrom ( 'S' ) );

	for ( const alphabet::RankedSymbol & symbol : pattern.getAlphabet ( ) ) {
		res.addInputSymbol ( alphabet::Symbol { symbol } );
		res.setPushdownStoreOperation ( alphabet::Symbol { symbol }, std::vector < alphabet::Symbol > { 1, alphabet::symbolFrom ( 'S' ) }, std::vector < alphabet::Symbol > { symbol.getRank ( ).getData ( ), alphabet::symbolFrom ( 'S' ) } );
	}

	for ( const alphabet::RankedSymbol & symbol : pattern.getAlphabet ( ) ) {
		res.addTransition ( automaton::State ( 0 ), alphabet::Symbol { symbol }, automaton::State ( 0 ) );
	}

	int i = 1;

	for ( const alphabet::RankedSymbol & symbol : pattern.getContent ( ) ) {
		res.addState ( automaton::State ( i ) );
		res.addTransition ( automaton::State ( i - 1 ), alphabet::Symbol { symbol }, automaton::State ( i ) );
		i++;
	}

	res.addFinalState ( automaton::State ( i - 1 ) );
	return res;
}

auto ExactSubtreeMatchingAutomatonPrefixRankedTree = ExactSubtreeMatchingAutomaton::RegistratorWrapper < automaton::InputDrivenNPDA, tree::PrefixRankedTree > ( ExactSubtreeMatchingAutomaton::construct );

automaton::InputDrivenNPDA ExactSubtreeMatchingAutomaton::construct ( const tree::PrefixRankedBarTree & pattern ) {
	automaton::InputDrivenNPDA res ( automaton::State ( 0 ), alphabet::Symbol { alphabet::BottomOfTheStackSymbol::BOTTOM_OF_THE_STACK } );

	res.setStackAlphabet ( { alphabet::Symbol { alphabet::BottomOfTheStackSymbol::BOTTOM_OF_THE_STACK }, alphabet::symbolFrom ( 'S' ) } );

	for ( const alphabet::RankedSymbol & symbol : pattern.getAlphabet ( ) ) {
		res.addInputSymbol ( alphabet::Symbol { symbol } );

		if ( symbol.getSymbol ( ) == pattern.getBarSymbol ( ) )
			res.setPushdownStoreOperation ( alphabet::Symbol { symbol }, std::vector < alphabet::Symbol > { 1, alphabet::symbolFrom ( 'S' ) }, std::vector < alphabet::Symbol > { } );
		else
			res.setPushdownStoreOperation ( alphabet::Symbol { symbol }, std::vector < alphabet::Symbol > { }, std::vector < alphabet::Symbol > { 1, alphabet::symbolFrom ( 'S' ) } );
	}

	for ( const alphabet::RankedSymbol & symbol : pattern.getAlphabet ( ) ) {
		res.addTransition ( automaton::State ( 0 ), alphabet::Symbol { symbol }, automaton::State ( 0 ) );
	}

	int i = 1;

	for ( const alphabet::RankedSymbol & symbol : pattern.getContent ( ) ) {
		res.addState ( automaton::State ( i ) );
		res.addTransition ( automaton::State ( i - 1 ), alphabet::Symbol { symbol }, automaton::State ( i ) );
		i++;
	}

	res.addFinalState ( automaton::State ( i - 1 ) );
	return res;
}

auto ExactSubtreeMatchingAutomatonPrefixRankedBarTree = ExactSubtreeMatchingAutomaton::RegistratorWrapper < automaton::InputDrivenNPDA, tree::PrefixRankedBarTree > ( ExactSubtreeMatchingAutomaton::construct );

automaton::State constructRecursive ( const tree::RankedNode & node, automaton::NFTA & res, int & nextState ) {
	std::vector < automaton::State > states;

	states.reserve ( node.getSymbol ( ).getRank ( ).getData ( ) );

	for ( const auto & child : node.getChildren ( ) )
		states.push_back ( constructRecursive ( * child, res, nextState ) );

	automaton::State state ( nextState++ );
	res.addState ( state );
	res.addTransition ( node.getSymbol ( ), states, state );
	return state;
}

automaton::NFTA ExactSubtreeMatchingAutomaton::construct ( const tree::RankedTree & pattern ) {
	automaton::NFTA res;

	res.setInputSymbols ( pattern.getAlphabet ( ) );
	int nextState = 0;
	res.addFinalState ( constructRecursive ( pattern.getRoot ( ), res, nextState ) );
	return res;
}

auto ExactSubtreeMatchingAutomatonRankedTree = ExactSubtreeMatchingAutomaton::RegistratorWrapper < automaton::NFTA, tree::RankedTree > ( ExactSubtreeMatchingAutomaton::construct );

} /* namespace exact */

} /* namespace arbology */