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 <alib/deque>
#include <registration/AlgoRegistration.hpp>

namespace arbology {

namespace exact {

automaton::InputDrivenNPDA < > ExactSubtreeMatchingAutomaton::construct ( const tree::PrefixRankedTree < > & pattern ) {
	automaton::InputDrivenNPDA < > res ( DefaultStateType ( 0 ), DefaultSymbolType ( 'S' ) );

	for ( const common::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		res.addInputSymbol ( DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ) );
		res.setPushdownStoreOperation ( DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), ext::vector < DefaultSymbolType > ( 1, DefaultSymbolType ( 'S' ) ), ext::vector < DefaultSymbolType > ( ( size_t ) symbol.getRank ( ), DefaultSymbolType ( 'S' ) ) );
	}

	for ( const common::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		res.addTransition ( DefaultStateType ( 0 ), DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), DefaultStateType ( 0 ) );
	}

	int i = 1;

	for ( const common::ranked_symbol < > & symbol : pattern.getContent ( ) ) {
		res.addState ( DefaultStateType ( i ) );
		res.addTransition ( DefaultStateType ( i - 1 ), DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), DefaultStateType ( i ) );
		i++;
	}

	res.addFinalState ( DefaultStateType ( i - 1 ) );
	return res;
}

auto ExactSubtreeMatchingAutomatonPrefixRankedTree = registration::AbstractRegister < ExactSubtreeMatchingAutomaton, automaton::InputDrivenNPDA < >, const tree::PrefixRankedTree < > & > ( ExactSubtreeMatchingAutomaton::construct );

automaton::InputDrivenNPDA < > ExactSubtreeMatchingAutomaton::construct ( const tree::PrefixRankedBarTree < > & pattern ) {
	automaton::InputDrivenNPDA < > res ( DefaultStateType ( 0 ), alphabet::BottomOfTheStackSymbol::instance < DefaultSymbolType > ( ) );

	res.setPushdownStoreAlphabet ( { alphabet::BottomOfTheStackSymbol::instance < DefaultSymbolType > ( ), DefaultSymbolType ( 'S' ) } );

	for ( const common::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		res.addInputSymbol ( DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ) );

		if ( pattern.getBars ( ).count ( symbol ) )
			res.setPushdownStoreOperation ( DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), ext::vector < DefaultSymbolType > ( 1, DefaultSymbolType ( 'S' ) ), ext::vector < DefaultSymbolType > { } );
		else
			res.setPushdownStoreOperation ( DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), ext::vector < DefaultSymbolType > { }, ext::vector < DefaultSymbolType > ( 1, DefaultSymbolType ( 'S' ) ) );
	}

	for ( const common::ranked_symbol < > & symbol : pattern.getAlphabet ( ) ) {
		res.addTransition ( DefaultStateType ( 0 ), DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), DefaultStateType ( 0 ) );
	}

	int i = 1;

	for ( const common::ranked_symbol < > & symbol : pattern.getContent ( ) ) {
		res.addState ( DefaultStateType ( i ) );
		res.addTransition ( DefaultStateType ( i - 1 ), DefaultSymbolType ( alphabet::RankedSymbol < > { symbol } ), DefaultStateType ( i ) );
		i++;
	}

	res.addFinalState ( DefaultStateType ( i - 1 ) );
	return res;
}

auto ExactSubtreeMatchingAutomatonPrefixRankedBarTree = registration::AbstractRegister < ExactSubtreeMatchingAutomaton, automaton::InputDrivenNPDA < >, const tree::PrefixRankedBarTree < > & > ( ExactSubtreeMatchingAutomaton::construct );

DefaultStateType constructRecursive ( const ext::tree < common::ranked_symbol < > > & node, automaton::NFTA < > & res, int & nextState ) {
	ext::vector < DefaultStateType > states;

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

	for ( const ext::tree < common::ranked_symbol < > > & child : node.getChildren ( ) )
		states.push_back ( constructRecursive ( child, res, nextState ) );

	DefaultStateType state = DefaultStateType ( nextState++ );
	res.addState ( state );
	res.addTransition ( node.getData ( ), states, state );
	return state;
}

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

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

auto ExactSubtreeMatchingAutomatonRankedTree = registration::AbstractRegister < ExactSubtreeMatchingAutomaton, automaton::NFTA < >, const tree::RankedTree < > & > ( ExactSubtreeMatchingAutomaton::construct );

} /* namespace exact */

} /* namespace arbology */