NFA.h

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

#ifndef NFA_H_
#define NFA_H_

#include <map>
#include "../../std/map.hpp"
#include "../AutomatonBase.h"
#include "../common/MultiInitialStates.h"
#include "../common/InputAlphabet.h"
#include "../../alphabet/Symbol.h"

namespace automaton {

/**
 * Represents Finite Automaton.
 * Can store nondeterministic finite automaton without epsilon transitions.
 */
class NFA : public std::element<NFA, AutomatonBase>, public MultiInitialStates, public InputAlphabet {
protected:
	std::map<std::pair<State, alphabet::Symbol>, std::set<State> > transitions;
public:
	virtual AutomatonBase* clone() const;
	
	virtual AutomatonBase* plunder() &&;

	/**
	 * @copydoc Automaton::removeState(const State&)
	 */
	virtual bool removeState(const State& state);

	/**
	 * @copydoc Automaton::removeInputSymbol(const Symbol&)
	 */
	virtual bool removeInputSymbol(const alphabet::Symbol& symbol);
	
	/**
	 * Adds transition defined by parameters to the automaton.
	 * @param current current state
	 * @param input input symbol
	 * @param next next state
	 * @throws AutomatonException when transition already exists or when transition contains state or symbol not present in the automaton
	 */
	bool addTransition(const State& current, const alphabet::Symbol& input, const State& next);

	/**
	 * Removes transition from the automaton.
	 * @param transition transition to remove
	 * @throws AutomatonException when transition doesn't exists.
	 */
	bool removeTransition(const State& current, const alphabet::Symbol& input, const State& next);

	/**
	 * @return automaton transitions
	 */
	const std::map<std::pair<State, alphabet::Symbol>, std::set<State> >& getTransitions() const;

	/**
	 * @return automaton transitions from state
	 */
	std::map<std::pair<State, alphabet::Symbol>, std::set<State> > getTransitionsFromState(const State& from) const;
	
	/**
	 * @return automaton transitions to state
	 */
	std::map<std::pair<State, alphabet::Symbol>, std::set<State> > getTransitionsToState(const State& from) const;
	
	/**
	 * Determines whether NFA is deterministic.
	 * FA is deterministic if and only if:
	 * \li \c contains only 1 initial state.
	 * \li \c is epsilon free. Trivial for this class
	 * \li \c size of transition function \delta (from state, input symbol) \leq 1
	 * @return true when automaton is deterministic, false otherwise
	 */
	bool isDeterministic() const;

	/**
	 * Determines whether NFA is total deterministic
	 * FA is deterministic if and only if
	 * \li \c it is deterministic
	 * \li \c size of transition function \forall states and \forall input symbols \delta (from state, input symbol) = 1
	 * @return true when automaton is total deterministic, false otherwise
	 */
	bool isTotal() const;

	virtual bool operator==(const AutomatonBase& other) const;

	virtual bool operator==(const NFA& other) const;

	virtual void operator>>(std::ostream& os) const;
};

} /* namespace automaton */

#endif /* NFA_H_ */