Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
UnorderedNFTA.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <ostream>
27
28#include <alib/multimap>
29#include <alib/set>
30#include <alib/multiset>
31
32#include <core/components.hpp>
33
34#include <core/normalize.hpp>
35
38
40
41#include <core/normalize.hpp>
44
45#include "UnorderedDFTA.h"
46
47namespace automaton {
48
49class InputAlphabet;
50class States;
51class FinalStates;
52
71template < class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType >
72class UnorderedNFTA final : public core::Components < UnorderedNFTA < SymbolTypeT, StateTypeT >, ext::set < common::ranked_symbol < SymbolTypeT > >, component::Set, InputAlphabet, ext::set < StateTypeT >, component::Set, std::tuple < States, FinalStates > > {
73public:
74 typedef SymbolTypeT SymbolType;
75 typedef StateTypeT StateType;
76
77private:
82
83public:
87 explicit UnorderedNFTA ( );
88
97
98 /*
99 * \brief Creates a new instance of the automaton based on the Deterministic finite tree automaton.
100 *
101 * \param other the Deterministic finite tree automaton
102 */
104
110 const ext::set < StateType > & getStates ( ) const & {
111 return this->template accessComponent < States > ( ).get ( );
112 }
113
120 return std::move ( this->template accessComponent < States > ( ).get ( ) );
121 }
122
130 bool addState ( StateType state ) {
131 return this->template accessComponent < States > ( ).add ( std::move ( state ) );
132 }
133
140 this->template accessComponent < States > ( ).set ( std::move ( states ) );
141 }
142
150 void removeState ( const StateType & state ) {
151 this->template accessComponent < States > ( ).remove ( state );
152 }
153
160 return this->template accessComponent < FinalStates > ( ).get ( );
161 }
162
169 return std::move ( this->template accessComponent < FinalStates > ( ).get ( ) );
170 }
171
179 bool addFinalState ( StateType state ) {
180 return this->template accessComponent < FinalStates > ( ).add ( std::move ( state ) );
181 }
182
189 this->template accessComponent < FinalStates > ( ).set ( std::move ( states ) );
190 }
191
199 void removeFinalState ( const StateType & state ) {
200 this->template accessComponent < FinalStates > ( ).remove ( state );
201 }
202
209 return this->template accessComponent < InputAlphabet > ( ).get ( );
210 }
211
218 return std::move ( this->template accessComponent < InputAlphabet > ( ).get ( ) );
219 }
220
229 return this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbol ) );
230 }
231
238 this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbols ) );
239 }
240
247 this->template accessComponent < InputAlphabet > ( ).set ( std::move ( symbols ) );
248 }
249
258 this->template accessComponent < InputAlphabet > ( ).remove ( symbol );
259 }
260
275
287 bool removeTransition ( const common::ranked_symbol < SymbolType > & symbol, const ext::multiset < StateType > & states, const StateType & next );
288
295 return transitions;
296 }
297
304 return std::move ( transitions );
305 }
306
312
313 for ( const auto & transition : getTransitions ( ) )
314 if ( transition.second == q )
315 res.insert ( transition );
316
317 return res;
318 }
319
325
326 for ( const auto & transition : getTransitions ( ) ) {
327 if ( std::find ( transition.first.second.begin ( ), transition.first.second.end ( ), q ) != transition.first.second.end ( ) )
328 res.insert ( transition );
329 }
330
331 return res;
332 }
333
342 bool isDeterministic ( ) const;
343
351 auto operator <=> ( const UnorderedNFTA & other ) const {
352 return std::tie(getStates(), getInputAlphabet(), getFinalStates(), transitions) <=> std::tie(other.getStates(), other.getInputAlphabet(), other.getFinalStates(), other.transitions);
353 }
354
362 bool operator == ( const UnorderedNFTA & other ) const {
363 return std::tie(getStates(), getInputAlphabet(), getFinalStates(), transitions) == std::tie(other.getStates(), other.getInputAlphabet(), other.getFinalStates(), other.transitions);
364 }
365
374 friend ext::ostream & operator << ( ext::ostream & out, const UnorderedNFTA & instance ) {
375 return out << "(UnorderedNFTA"
376 << " states = " << instance.getStates ( )
377 << " inputAlphabet = " << instance.getInputAlphabet ( )
378 << " finalStates = " << instance.getFinalStates ( )
379 << " transitions = " << instance.getTransitions ( )
380 << ")";
381 }
382};
383
389template < class T >
390class isUnorderedNFTA_impl : public std::false_type {};
391
400template < class SymbolType, class StateType >
401class isUnorderedNFTA_impl < UnorderedNFTA < SymbolType, StateType > > : public std::true_type {};
402
408template < class T >
410
411template < class SymbolType, class StateType >
412UnorderedNFTA < SymbolType, StateType >::UnorderedNFTA ( ext::set < StateType > states, ext::set < common::ranked_symbol < SymbolType > > inputAlphabet, ext::set < StateType > finalStates ) : core::Components < UnorderedNFTA, 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 ) ) {
413}
414
415template < class SymbolType, class StateType >
417}
418
419template < class SymbolType, class StateType >
420UnorderedNFTA < SymbolType, StateType >::UnorderedNFTA(const UnorderedDFTA < SymbolType, StateType > & other) : UnorderedNFTA ( other.getStates(), other.getInputAlphabet(), other.getFinalStates() ) {
421 transitions.insert ( other.getTransitions ( ).begin ( ), other.getTransitions ( ).end ( ) );
422}
423
424template < class SymbolType, class StateType >
426 if ( prevStates.size ( ) != symbol.getRank ( ) )
427 throw AutomatonException("Number of states doesn't match rank of the symbol");
428
429 if (! getInputAlphabet().count(symbol))
430 throw AutomatonException("Input symbol \"" + ext::to_string ( symbol ) + "\" doesn't exist.");
431
432 if (! getStates().count(next))
433 throw AutomatonException("State \"" + ext::to_string ( next ) + "\" doesn't exist.");
434
435 for (const StateType& it : prevStates) {
436 if (! getStates().count(it))
437 throw AutomatonException("State \"" + ext::to_string ( it ) + "\" doesn't exist.");
438 }
439
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 )
444 return false;
445
446 ext::pair < common::ranked_symbol < SymbolType >, ext::multiset < StateType > > key = ext::make_pair ( std::move ( symbol ), std::move ( prevStates ) );
447 transitions.insert ( iter, std::make_pair ( std::move ( key ), std::move ( next ) ) );
448 return true;
449}
450
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 )
457 return false;
458
459 transitions.erase ( iter );
460 return true;
461}
462
463template < class SymbolType, class StateType >
465 if ( transitions.empty ( ) )
466 return true;
467
468 for ( auto iter = transitions.begin ( ); std::next ( iter ) != transitions.end ( ); ++ iter )
469 if ( iter->first == std::next ( iter )->first )
470 return false;
471
472 return true;
473}
474
475} /* namespace automaton */
476
477namespace core {
478
485template < class SymbolType, class StateType >
486class SetConstraint< automaton::UnorderedNFTA < SymbolType, StateType >, common::ranked_symbol < SymbolType >, automaton::InputAlphabet > {
487public:
497 for ( const std::pair<const ext::pair<common::ranked_symbol < SymbolType >, ext::multiset<StateType> >, StateType > & t : automaton.getTransitions())
498 if (t.first.first == symbol)
499 return true;
500
501 return false;
502 }
503
513 return true;
514 }
515
523 }
524};
525
532template < class SymbolType, class StateType >
533class SetConstraint< automaton::UnorderedNFTA < SymbolType, StateType >, StateType, automaton::States > {
534public:
544 if ( automaton.getFinalStates ( ).count ( state ) )
545 return true;
546
547 for ( const std::pair<const ext::pair<common::ranked_symbol < SymbolType >, ext::multiset<StateType> >, StateType >& t : automaton.getTransitions())
548 if(ext::contains(t.first.second.begin(), t.first.second.end(), state ) || t . second == state )
549 return true;
550
551 return false;
552 }
553
563 return true;
564 }
565
573 }
574};
575
582template < class SymbolType, class StateType >
583class SetConstraint< automaton::UnorderedNFTA < SymbolType, StateType >, StateType, automaton::FinalStates > {
584public:
594 return false;
595 }
596
606 return automaton.template accessComponent < automaton::States > ( ).get ( ).count ( state );
607 }
608
616 }
617};
618
624template < class SymbolType, class StateType >
625struct normalize < automaton::UnorderedNFTA < SymbolType, StateType > > {
628 ext::set < DefaultStateType > states = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getStates ( ) );
629 ext::set < DefaultStateType > finalStates = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getFinalStates ( ) );
630
631 automaton::UnorderedNFTA < > res ( std::move ( states ), std::move ( alphabet ), std::move ( finalStates ) );
632
633 for ( std::pair < ext::pair < common::ranked_symbol < SymbolType >, ext::multiset < StateType > >, StateType > && transition : ext::make_mover ( std::move ( value ).getTransitions ( ) ) ) {
635 ext::multiset < DefaultStateType > from = automaton::AutomatonNormalize::normalizeStates ( std::move ( transition.first.second ) );
636 DefaultStateType to = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second ) );
637
638 res.addTransition ( std::move ( input ), std::move ( from ), std::move ( to ) );
639 }
640
641 return res;
642 }
643};
644
645} /* namespace core */
646
647extern template class automaton::UnorderedNFTA < >;
648
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
Deterministic unordered finite tree automaton without epsilon transitions. Accepts regular tree langu...
Definition: UnorderedDFTA.h:72
Nondeterministic unordered finite tree automaton without epsilon transitions. Accepts regular tree la...
Definition: UnorderedNFTA.h:72
bool addFinalState(StateType state)
Definition: UnorderedNFTA.h:179
bool addInputSymbol(common::ranked_symbol< SymbolType > symbol)
Definition: UnorderedNFTA.h:228
ext::set< StateType > && getFinalStates() &&
Definition: UnorderedNFTA.h:168
void removeFinalState(const StateType &state)
Definition: UnorderedNFTA.h:199
bool removeTransition(const common::ranked_symbol< SymbolType > &symbol, const ext::multiset< StateType > &states, const StateType &next)
Removes a transition from the automaton.
Definition: UnorderedNFTA.h:452
bool addTransition(common::ranked_symbol< SymbolType > symbol, ext::multiset< StateType > prevStates, StateType next)
Add a transition to the automaton.
Definition: UnorderedNFTA.h:425
const ext::set< StateType > & getStates() const &
Definition: UnorderedNFTA.h:110
bool operator==(const UnorderedNFTA &other) const
Definition: UnorderedNFTA.h:362
UnorderedNFTA()
Creates a new instance of the automaton.
Definition: UnorderedNFTA.h:416
const ext::set< StateType > & getFinalStates() const &
Definition: UnorderedNFTA.h:159
auto operator<=>(const UnorderedNFTA &other) const
Definition: UnorderedNFTA.h:351
void removeState(const StateType &state)
Definition: UnorderedNFTA.h:150
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::multiset< StateType > >, StateType > getTransitionsFromState(const StateType &q) const
Definition: UnorderedNFTA.h:323
bool isDeterministic() const
Determines whether the automaton is deterministic.
Definition: UnorderedNFTA.h:464
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::multiset< StateType > >, StateType > && getTransitions() &&
Definition: UnorderedNFTA.h:303
void setStates(ext::set< StateType > states)
Definition: UnorderedNFTA.h:139
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::multiset< StateType > >, StateType > getTransitionsToState(const StateType &q) const
Definition: UnorderedNFTA.h:310
void addInputSymbols(ext::set< common::ranked_symbol< SymbolType > > symbols)
Definition: UnorderedNFTA.h:237
ext::set< common::ranked_symbol< SymbolType > > && getInputAlphabet() &&
Definition: UnorderedNFTA.h:217
void setFinalStates(ext::set< StateType > states)
Definition: UnorderedNFTA.h:188
SymbolTypeT SymbolType
Definition: UnorderedNFTA.h:74
const ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::multiset< StateType > >, StateType > & getTransitions() const &
Definition: UnorderedNFTA.h:294
StateTypeT StateType
Definition: UnorderedNFTA.h:75
void setInputAlphabet(ext::set< common::ranked_symbol< SymbolType > > symbols)
Definition: UnorderedNFTA.h:246
void removeInputSymbol(const common::ranked_symbol< SymbolType > &symbol)
Definition: UnorderedNFTA.h:257
friend ext::ostream & operator<<(ext::ostream &out, const UnorderedNFTA &instance)
Definition: UnorderedNFTA.h:374
const ext::set< common::ranked_symbol< SymbolType > > & getInputAlphabet() const &
Definition: UnorderedNFTA.h:208
ext::set< StateType > && getStates() &&
Definition: UnorderedNFTA.h:119
bool addState(StateType state)
Definition: UnorderedNFTA.h:130
Definition: UnorderedNFTA.h:390
Definition: ranked_symbol.hpp:20
Definition: components.hpp:181
static void valid(const automaton::UnorderedNFTA< SymbolType, StateType > &, const StateType &)
Definition: UnorderedNFTA.h:615
static bool available(const automaton::UnorderedNFTA< SymbolType, StateType > &automaton, const StateType &state)
Definition: UnorderedNFTA.h:605
static bool used(const automaton::UnorderedNFTA< SymbolType, StateType > &, const StateType &)
Definition: UnorderedNFTA.h:593
static void valid(const automaton::UnorderedNFTA< SymbolType, StateType > &, const common::ranked_symbol< SymbolType > &)
Definition: UnorderedNFTA.h:522
static bool used(const automaton::UnorderedNFTA< SymbolType, StateType > &automaton, const common::ranked_symbol< SymbolType > &symbol)
Definition: UnorderedNFTA.h:496
static bool available(const automaton::UnorderedNFTA< SymbolType, StateType > &, const common::ranked_symbol< SymbolType > &)
Definition: UnorderedNFTA.h:512
static bool used(const automaton::UnorderedNFTA< SymbolType, StateType > &automaton, const StateType &state)
Definition: UnorderedNFTA.h:543
static void valid(const automaton::UnorderedNFTA< SymbolType, StateType > &, const StateType &)
Definition: UnorderedNFTA.h:572
static bool available(const automaton::UnorderedNFTA< SymbolType, StateType > &, const StateType &)
Definition: UnorderedNFTA.h:562
Definition: setComponents.hpp:26
Class extending the multimap class from the standard library. Original reason is to allow printing of...
Definition: multimap.hpp:48
Definition: multiset.hpp:44
Definition: ostream.h:14
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
Definition: Object.h:16
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 isUnorderedNFTA
Definition: UnorderedNFTA.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 &param)
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::UnorderedNFTA< > eval(automaton::UnorderedNFTA< SymbolType, StateType > &&value)
Definition: UnorderedNFTA.h:626
Definition: normalize.hpp:13