NFA.cpp

/*
 * NFA.cpp
 *
 *  Created on: Mar 25, 2013
 *      Author: Jan Travnicek
 */

#include "NFA.h"
#include "../AutomatonException.h"
#include <ostream>
#include <sstream>

#include <sax/FromXMLParserHelper.h>
#include "../common/AutomatonFromXMLParser.h"
#include "../common/AutomatonToXMLComposer.h"
#include "../Automaton.h"
#include <object/Object.h>
#include <XmlApi.hpp>
#include <cast/CastApi.hpp>

namespace automaton {

NFA::NFA(State initialState) : SingleInitialState(std::move(initialState)) {

}

NFA::NFA(const DFA& other) : SingleInitialState(other.getInitialState()) {
	inputAlphabet = other.getInputAlphabet();
	states = other.getStates();
	finalStates = other.getFinalStates();
	for(const auto& transition : other.getTransitions()) {
		transitions[transition.first].insert(transition.second);
	}
}

AutomatonBase* NFA::clone() const {
	return new NFA(*this);
}

AutomatonBase* NFA::plunder() && {
	return new NFA(std::move(*this));
}

bool NFA::removeState(const State& state) {
	if (initialState == state) {
		throw AutomatonException("State \"" + (std::string) state.getName() + "\" is initial state.");
	}

	if (finalStates.find(state) != finalStates.end()) {
		throw AutomatonException("State \"" + (std::string) state.getName() + "\" is final state.");
	}

	for (const std::pair<const std::pair<State, alphabet::Symbol>, std::set<State> >& transition : transitions) {
		if (transition.first.first == state || transition.second.find(state) != transition.second.end())
			throw AutomatonException("State \"" + (std::string) state.getName() + "\" is used in transition.");
	}

	return states.erase(state);
}

bool NFA::removeInputSymbol(const alphabet::Symbol& symbol) {
	for (const std::pair<const std::pair<State, alphabet::Symbol>, std::set<State> >& transition : transitions) {
		if (transition.first.second == symbol)
			throw AutomatonException("Input symbol \"" + (std::string) symbol + "\" is used.");
	}

	return inputAlphabet.erase(symbol);
}

bool NFA::addTransition(State from, alphabet::Symbol input, State to) {
	if (states.find(from) == states.end())
		throw AutomatonException("State \"" + (std::string) from.getName() + "\" doesn't exist.");

	if (inputAlphabet.find(input) == inputAlphabet.end())
		throw AutomatonException("Input symbol \"" + (std::string) input + "\" doesn't exist.");

	if (states.find(to) == states.end())
		throw AutomatonException("State \"" + (std::string) to.getName() + "\" doesn't exist.");

	std::pair<State, alphabet::Symbol> key = std::make_pair(std::move(from), std::move(input));

	return transitions[std::move(key)].insert(std::move(to)).second;
}

bool NFA::removeTransition(const State& from, const alphabet::Symbol& input, const State& to) {
	std::pair<State, alphabet::Symbol> key = std::make_pair(from, input);

	return transitions[key].erase(to);
}

const std::map<std::pair<State, alphabet::Symbol>, std::set<State> >& NFA::getTransitions() const {
	return transitions;
}

std::map<std::pair<State, alphabet::Symbol>, std::set<State> > NFA::getTransitionsFromState(const State& from) const {
	if( states.find(from) == states.end())
		throw AutomatonException("State \"" + (std::string) from.getName() + "\" doesn't exist");

	std::map<std::pair<State, alphabet::Symbol>, std::set<State> > transitionsFromState;
	for (const std::pair<const std::pair<State, alphabet::Symbol>, std::set<State> >& transition : transitions) {
		if (transition.first.first == from)
			transitionsFromState[transition.first].insert(transition.second.begin(), transition.second.end());
	}

	return transitionsFromState;
}

std::map<std::pair<State, alphabet::Symbol>, std::set<State> > NFA::getTransitionsToState(const State& to) const {
	if( states.find(to) == states.end())
		throw AutomatonException("State \"" + (std::string) to.getName() + "\" doesn't exist");

	std::map<std::pair<State, alphabet::Symbol>, std::set<State> > transitionsToState;
	for (const std::pair<const std::pair<State, alphabet::Symbol>, std::set<State> >& transition : transitions) {
		if (transition.second.find(to) != transition.second.end())
			transitionsToState[transition.first].insert(transition.second.begin(), transition.second.end());
	}

	return transitionsToState;
}

bool NFA::isDeterministic() const {
	for (const std::pair<const std::pair<State, alphabet::Symbol>, std::set<State> >& transition : transitions) {
		if (transition.second.size() != 1 || transition.second.size() != 0)
			return false;
	}

	return true;
}

bool NFA::isTotal() const {
	return isDeterministic() && transitionsSize() == inputAlphabet.size() * states.size();
}

unsigned NFA::transitionsSize() const {
	int res = 0;
	for(const auto& transition : transitions ){
		res += transition.second.size();
	}
	return res;
}

int NFA::compare(const NFA& other) const {
	auto first = std::tie(states, inputAlphabet, initialState, finalStates, transitions);
	auto second = std::tie(other.states, other.inputAlphabet, other.initialState, other.finalStates, other.transitions);

	std::compare<decltype(first)> comp;
	return comp(first, second);
}

void NFA::operator>>(std::ostream& out) const {
	out << "(NFA "
		<< " states = " << states
		<< " inputAlphabet = " << inputAlphabet
		<< " initialState = " << initialState
		<< " finalStates = " << finalStates
		<< " transitions = " << transitions
		<< ")";
}

NFA::operator std::string () const {
	std::stringstream ss;
	ss << *this;
	return ss.str();
}

const std::string NFA::XML_TAG_NAME = "NFA";

NFA NFA::parse(std::deque<sax::Token>::iterator& input) {
	sax::FromXMLParserHelper::popToken(input, sax::Token::TokenType::START_ELEMENT, NFA::XML_TAG_NAME);

	std::set<State> states = AutomatonFromXMLParser::parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = AutomatonFromXMLParser::parseInputAlphabet(input);
	State initialState = AutomatonFromXMLParser::parseInitialState(input);
	std::set<State> finalStates = AutomatonFromXMLParser::parseFinalStates(input);

	NFA automaton(std::move(initialState));
	automaton.setStates(std::move(states));
	automaton.setInputAlphabet(std::move(inputSymbols));
	automaton.setFinalStates(std::move(finalStates));

	AutomatonFromXMLParser::parseTransitions<NFA>(input, automaton);

	sax::FromXMLParserHelper::popToken(input, sax::Token::TokenType::END_ELEMENT, NFA::XML_TAG_NAME);
	return automaton;
}

void NFA::parseTransition(std::deque<sax::Token>::iterator& input, NFA& automaton) {
	sax::FromXMLParserHelper::popToken(input, sax::Token::TokenType::START_ELEMENT, "transition");
	State from = AutomatonFromXMLParser::parseTransitionFrom(input);
	alphabet::Symbol inputSymbol = AutomatonFromXMLParser::parseTransitionInputSymbol(input);
	State to = AutomatonFromXMLParser::parseTransitionTo(input);
	sax::FromXMLParserHelper::popToken(input, sax::Token::TokenType::END_ELEMENT, "transition");

	automaton.addTransition(std::move(from), std::move(inputSymbol), std::move(to));
}

void NFA::compose(std::deque<sax::Token>& out) const {
	out.emplace_back(NFA::XML_TAG_NAME, sax::Token::TokenType::START_ELEMENT);

	AutomatonToXMLComposer::composeStates(out, this->getStates());
	AutomatonToXMLComposer::composeInputAlphabet(out, this->getInputAlphabet());
	AutomatonToXMLComposer::composeInitialState(out, this->getInitialState());
	AutomatonToXMLComposer::composeFinalStates(out, this->getFinalStates());
	composeTransitions(out);

	out.emplace_back(NFA::XML_TAG_NAME, sax::Token::TokenType::END_ELEMENT);
}

void NFA::composeTransitions(std::deque<sax::Token>& out) const {
	out.emplace_back("transitions", sax::Token::TokenType::START_ELEMENT);
	for(const auto& transition : this->getTransitions()) {
		for(const auto& targetState: transition.second) {
			out.emplace_back("transition", sax::Token::TokenType::START_ELEMENT);

			AutomatonToXMLComposer::composeTransitionFrom(out, transition.first.first);
			AutomatonToXMLComposer::composeTransitionInputSymbol(out, transition.first.second);
			AutomatonToXMLComposer::composeTransitionTo(out, targetState);

			out.emplace_back("transition", sax::Token::TokenType::END_ELEMENT);
		}
	}

	out.emplace_back("transitions", sax::Token::TokenType::END_ELEMENT);
}

} /* namespace automaton */

namespace alib {

auto NFAParserRegister = xmlApi<automaton::Automaton>::ParserRegister<automaton::NFA>();
auto NFAParserRegister2 = xmlApi<alib::Object>::ParserRegister<automaton::NFA>();

auto NFAFromDFA = castApi::CastRegister<automaton::NFA, automaton::DFA>();
auto NFACastBinder = castApi::CastPoolStringBinder<automaton::NFA>(automaton::NFA::XML_TAG_NAME);

} /* namespace alib */