ExactSubtreeMatchingAutomaton.cpp

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

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

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

#include <deque>

namespace arbology {

namespace exact {

automaton::Automaton ExactSubtreeMatchingAutomaton::construct(const tree::Tree& pattern) {
	return getInstance().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::getInstance(), 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::getInstance(), ExactSubtreeMatchingAutomaton::construct);

} /* namespace exact */

} /* namespace arbology */