28#include <alib/multimap>
71template <
class SymbolTypeT = DefaultSymbolType,
class StateTypeT = DefaultStateType >
72class NFTA final :
public core::Components < NFTA < SymbolTypeT, StateTypeT >, ext::set < common::ranked_symbol < SymbolTypeT > >, component::Set, InputAlphabet, ext::set < StateTypeT >, component::Set, std::tuple < States, FinalStates > > {
111 return this->
template accessComponent < States > ( ).get ( );
120 return std::move ( this->
template accessComponent < States > ( ).
get ( ) );
131 return this->
template accessComponent < States > ( ).add ( std::move ( state ) );
140 this->
template accessComponent < States > ( ).set ( std::move ( states ) );
151 this->
template accessComponent < States > ( ).remove ( state );
160 return this->
template accessComponent < FinalStates > ( ).get ( );
169 return std::move ( this->
template accessComponent < FinalStates > ( ).
get ( ) );
180 return this->
template accessComponent < FinalStates > ( ).add ( std::move ( state ) );
189 this->
template accessComponent < FinalStates > ( ).set ( std::move ( states ) );
200 this->
template accessComponent < FinalStates > ( ).remove ( state );
209 return this->
template accessComponent < InputAlphabet > ( ).get ( );
218 return std::move ( this->
template accessComponent < InputAlphabet > ( ).
get ( ) );
229 return this->
template accessComponent < InputAlphabet > ( ).add ( std::move ( symbol ) );
238 this->
template accessComponent < InputAlphabet > ( ).add ( std::move ( symbols ) );
247 this->
template accessComponent < InputAlphabet > ( ).set ( std::move ( symbols ) );
258 this->
template accessComponent < InputAlphabet > ( ).remove ( symbol );
304 return std::move ( transitions );
314 if ( transition.second ==
q )
315 res.insert ( transition );
327 if ( std::find ( transition.first.second.begin ( ), transition.first.second.end ( ),
q ) != transition.first.second.end ( ) )
328 res.insert ( transition );
375 return out <<
"(NFTA"
376 <<
" states = " << instance.
getStates ( )
400template <
class SymbolType,
class StateType >
411template <
class SymbolType,
class StateType >
412NFTA < SymbolType, StateType >::NFTA (
ext::set < StateType > states,
ext::set < common::ranked_symbol < SymbolType > > inputAlphabet,
ext::set < StateType > finalStates ) :
core::Components <
NFTA,
ext::set <
common::ranked_symbol < SymbolType > >, component::Set, InputAlphabet,
ext::set < StateType >, component::Set, std::tuple < States, FinalStates > > ( std::move ( inputAlphabet ), std::move ( states ), std::move ( finalStates ) ) {
415template <
class SymbolType,
class StateType >
419template <
class SymbolType,
class StateType >
421 transitions.insert ( other.getTransitions ( ).begin ( ), other.getTransitions ( ).end ( ) );
424template <
class SymbolType,
class StateType >
426 if ( prevStates.size ( ) != symbol.getRank ( ) )
429 if (! getInputAlphabet().count(symbol))
432 if (! getStates().count(next))
436 if (! getStates().count(it))
440 auto upper_bound = transitions.upper_bound (
ext::tie ( symbol, prevStates ) );
441 auto lower_bound = transitions.lower_bound (
ext::tie ( symbol, prevStates ) );
442 auto iter = std::lower_bound ( lower_bound, upper_bound, next, [ ] (
const auto & transition,
const auto & target ) {
return transition.second < target; } );
443 if ( iter != upper_bound && next >= iter->second )
447 transitions.insert ( iter,
std::make_pair ( std::move ( key ), std::move ( next ) ) );
451template <
class SymbolType,
class StateType >
453 auto upper_bound = transitions.upper_bound (
ext::tie ( symbol, states ) );
454 auto lower_bound = transitions.lower_bound (
ext::tie ( symbol, states ) );
455 auto iter = std::find_if ( lower_bound, upper_bound, [ & ] (
const auto & transition ) {
return transition.second == next; } );
456 if ( iter == upper_bound )
459 transitions.erase ( iter );
463template <
class SymbolType,
class StateType >
465 if ( transitions.empty ( ) )
468 for (
auto iter = transitions.begin ( ); std::next ( iter ) != transitions.end ( ); ++ iter )
469 if ( iter->first == std::next ( iter )->first )
485template <
class SymbolType,
class StateType >
498 if (t.first.first == symbol)
532template <
class SymbolType,
class StateType >
544 if (
automaton.getFinalStates ( ).count ( state ) )
548 if(
ext::contains(t.first.second.begin(), t.first.second.end(), state ) || t .
second == state )
582template <
class SymbolType,
class StateType >
606 return automaton.template accessComponent < automaton::States > ( ).get ( ).count ( state );
624template <
class SymbolType,
class StateType >
638 res.addTransition ( std::move ( input ), std::move ( from ), std::move ( to ) );
static common::ranked_symbol< DefaultSymbolType > normalizeRankedSymbol(common::ranked_symbol< SymbolType > &&symbol)
Definition: SymbolNormalize.h:81
static ext::set< common::ranked_symbol< DefaultSymbolType > > normalizeRankedAlphabet(ext::set< common::ranked_symbol< SymbolType > > &&symbols)
Definition: SymbolNormalize.h:59
Definition: AutomatonException.h:15
static DefaultStateType normalizeState(StateType &&state)
Definition: AutomatonNormalize.h:76
static ext::multiset< DefaultStateType > normalizeStates(ext::multiset< StateType > &&states)
Definition: AutomatonNormalize.h:49
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
bool operator==(const NFTA &other) const
Definition: NFTA.h:362
void removeFinalState(const StateType &state)
Definition: NFTA.h:199
bool addTransition(common::ranked_symbol< SymbolType > symbol, ext::vector< StateType > prevStates, StateType next)
Add a transition to the automaton.
Definition: NFTA.h:425
bool removeTransition(const common::ranked_symbol< SymbolType > &symbol, const ext::vector< StateType > &states, const StateType &next)
Removes a transition from the automaton.
Definition: NFTA.h:452
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > getTransitionsFromState(const StateType &q) const
Definition: NFTA.h:323
const ext::set< StateType > & getFinalStates() const &
Definition: NFTA.h:159
ext::set< StateType > && getFinalStates() &&
Definition: NFTA.h:168
bool addState(StateType state)
Definition: NFTA.h:130
void setFinalStates(ext::set< StateType > states)
Definition: NFTA.h:188
friend ext::ostream & operator<<(ext::ostream &out, const NFTA &instance)
Definition: NFTA.h:374
const ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions() const &
Definition: NFTA.h:294
NFTA()
Creates a new instance of the automaton.
Definition: NFTA.h:416
void removeInputSymbol(const common::ranked_symbol< SymbolType > &symbol)
Definition: NFTA.h:257
void removeState(const StateType &state)
Definition: NFTA.h:150
auto operator<=>(const NFTA &other) const
Definition: NFTA.h:351
const ext::set< StateType > & getStates() const &
Definition: NFTA.h:110
SymbolTypeT SymbolType
Definition: NFTA.h:74
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > && getTransitions() &&
Definition: NFTA.h:303
const ext::set< common::ranked_symbol< SymbolType > > & getInputAlphabet() const &
Definition: NFTA.h:208
void setStates(ext::set< StateType > states)
Definition: NFTA.h:139
StateTypeT StateType
Definition: NFTA.h:75
void addInputSymbols(ext::set< common::ranked_symbol< SymbolType > > symbols)
Definition: NFTA.h:237
ext::set< StateType > && getStates() &&
Definition: NFTA.h:119
bool addFinalState(StateType state)
Definition: NFTA.h:179
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > getTransitionsToState(const StateType &q) const
Definition: NFTA.h:310
void setInputAlphabet(ext::set< common::ranked_symbol< SymbolType > > symbols)
Definition: NFTA.h:246
ext::set< common::ranked_symbol< SymbolType > > && getInputAlphabet() &&
Definition: NFTA.h:217
bool addInputSymbol(common::ranked_symbol< SymbolType > symbol)
Definition: NFTA.h:228
bool isDeterministic() const
Determines whether the automaton is deterministic.
Definition: NFTA.h:464
Definition: ranked_symbol.hpp:20
Definition: components.hpp:181
static bool used(const automaton::NFTA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFTA.h:543
static void valid(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:572
static bool available(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:562
static void valid(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:615
static bool available(const automaton::NFTA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFTA.h:605
static bool used(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:593
static bool used(const automaton::NFTA< SymbolType, StateType > &automaton, const common::ranked_symbol< SymbolType > &symbol)
Definition: NFTA.h:496
static bool available(const automaton::NFTA< SymbolType, StateType > &, const common::ranked_symbol< SymbolType > &)
Definition: NFTA.h:512
static void valid(const automaton::NFTA< SymbolType, StateType > &, const common::ranked_symbol< SymbolType > &)
Definition: NFTA.h:522
Definition: setComponents.hpp:26
Class extending the multimap class from the standard library. Original reason is to allow printing of...
Definition: multimap.hpp:48
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
Definition: BarSymbol.cpp:12
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
p second
Definition: ToRegExpAlgebraic.h:126
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
return res
Definition: MinimizeByPartitioning.h:145
q
Definition: SingleInitialStateEpsilonTransition.h:85
Definition: ToGrammar.h:31
constexpr bool isNFTA
Definition: NFTA.h:409
Definition: normalize.hpp:10
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
reference_mover< T > make_mover(T ¶m)
Move adaptor construction function specialized to lvalue reference parameter.
Definition: iterator.hpp:468
bool contains(InputIt first, InputIt last, const Element &elem)
Linear version of search in a range of values.
Definition: algorithm.hpp:170
std::string to_string(const T &value)
To string method designated for objects that can be casted to string.
Definition: string.hpp:131
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
static automaton::NFTA< > eval(automaton::NFTA< SymbolType, StateType > &&value)
Definition: NFTA.h:626
Definition: normalize.hpp:13