NFA.cpp

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

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

namespace automaton {

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

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

bool NFA::removeState(const State& state) {
	if (initialStates.find(state) != initialStates.end()) {
		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 (std::map<std::pair<State, alphabet::Symbol>, std::set<State> >::const_iterator t = transitions.begin(); t != transitions.end(); t++) {
		if (t->first.first == state || t->second.find(state) != t->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 (std::map<std::pair<State, alphabet::Symbol>, std::set<State> >::const_iterator transition = transitions.begin(); transition != transitions.end();
			transition++) {
		if (transition->first.second == symbol)
			throw AutomatonException("Input symbol \"" + (std::string) symbol + "\" is used.");
	}

	return inputAlphabet.erase(symbol);
}

bool NFA::addTransition(const State& from, const alphabet::Symbol& input, const 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(from, input);
	
	return transitions[key].insert(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 (std::map<std::pair<State, alphabet::Symbol>, std::set<State> >::const_iterator transition = transitions.begin(); transition != transitions.end();
			transition++) {
		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 (std::map<std::pair<State, alphabet::Symbol>, std::set<State> >::const_iterator transition = transitions.begin(); transition != transitions.end();
			transition++) {
		if (transition->second.find(to) != transition->second.end()) {
			transitionsToState[transition->first].insert(transition->second.begin(), transition->second.end());
		}
	}

	return transitionsToState;
}

bool NFA::isDeterministic() const {
	if (initialStates.size() != 1) {
		return false;
	}

	for (std::map<std::pair<State, alphabet::Symbol>, std::set<State> >::const_iterator transition = transitions.begin(); transition != transitions.end();
			transition++) {
		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;
}

bool NFA::operator==(const ObjectBase& other) const {
	return other == *this;
}

bool NFA::operator<(const ObjectBase& other) const {
	return other > *this;
}

bool NFA::operator>(const ObjectBase& other) const {
	return other < *this;
}

bool NFA::operator==(const NFA& other) const {
	return this->states == other.states && this->inputAlphabet == other.inputAlphabet && this->initialStates == other.initialStates && this->finalStates == other.finalStates && this->transitions == other.transitions;
}

bool NFA::operator<(const NFA& other) const {
	return std::tie(states, inputAlphabet, initialStates, finalStates, transitions) < std::tie(other.states, other.inputAlphabet, other.initialStates, other.finalStates, other.transitions);
}

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

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

} /* namespace automaton */