Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
Result.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <string/LinearString.h>
9#include <tree/ranked/RankedTree.h>
10#include <label/FailStateLabel.h>
11
12#include "Run.h"
13#include <automaton/FSM/DFA.h>
14#include <automaton/TA/DFTA.h>
15#include <automaton/PDA/InputDrivenDPDA.h>
16#include <automaton/PDA/VisiblyPushdownDPDA.h>
17#include <automaton/PDA/RealTimeHeightDeterministicDPDA.h>
18#include <automaton/PDA/DPDA.h>
19
20#include <alib/deque>
21
22namespace automaton {
23
24namespace run {
25
30class Result {
31public:
43 template < class SymbolType, class StateType >
44 static StateType result ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
45
58 template < class SymbolType, class StateType >
59 static StateType result ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree );
60
61 template < class SymbolType, class StateType >
62 static StateType result ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree );
63
76 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
77 static StateType result ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
78
91 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
92 static StateType result ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
93
106 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
107 static StateType result ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
108
121 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
122 static StateType result ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
123
136 template < class SymbolType, class StateType >
137 static StateType result ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string, const StateType & failLabel );
138
152 template < class SymbolType, class StateType >
153 static StateType result ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree, const StateType & failLabel );
154
155 template < class SymbolType, class StateType >
156 static StateType result ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree, const StateType & failLabel );
157
171 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
172 static StateType result ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel );
173
187 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
188 static StateType result ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel );
189
203 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
204 static StateType result ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel );
205
219 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
220 static StateType result ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel );
221};
222
223template < class SymbolType, class StateType >
224StateType Result::result ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
225 return result ( automaton, string, label::FailStateLabel::instance < StateType > ( ) );
226}
227
228template < class SymbolType, class StateType >
229StateType Result::result ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree ) {
230 return result ( automaton, tree, label::FailStateLabel::instance < StateType > ( ) );
231}
232
233template < class SymbolType, class StateType >
234StateType Result::result ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree ) {
235 return result ( automaton, tree, label::FailStateLabel::instance < StateType> ( ) );
236}
237
238template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
239StateType Result::result ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
240 return result ( automaton, string, label::FailStateLabel::instance < StateType > ( ) );
241}
242
243template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
244StateType Result::result ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
245 return result ( automaton, string, label::FailStateLabel::instance < StateType > ( ) );
246}
247
248template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
249StateType Result::result ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
250 return result ( automaton, string, label::FailStateLabel::instance < StateType > ( ) );
251}
252
253template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
254StateType Result::result ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
255 return result ( automaton, string, label::FailStateLabel::instance < StateType > ( ) );
256}
257
258template < class SymbolType, class StateType >
259StateType Result::result ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string, const StateType & failLabel ) {
260 ext::tuple < bool, StateType, ext::set < unsigned > > res = Run::calculateState ( automaton, string );
261
262 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
263
264 return failLabel;
265}
266
267template < class SymbolType, class StateType >
268StateType Result::result ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree, const StateType & failLabel ) {
269 ext::tuple < bool, StateType, ext::set < unsigned > > res = Run::calculateState ( automaton, tree );
270
271 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
272
273 return failLabel;
274}
275
276template < class SymbolType, class StateType >
277StateType Result::result ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree, const StateType & failLabel ) {
278 ext::tuple < bool, StateType, ext::set < unsigned > > res = Run::calculateState ( automaton, tree );
279
280 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
281
282 return failLabel;
283}
284
285template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
286StateType Result::result ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel ) {
287 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
288
289 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
290
291 return failLabel;
292}
293
294template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
295StateType Result::result ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel ) {
296 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
297
298 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
299
300 return failLabel;
301}
302
303template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
304StateType Result::result ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel ) {
305 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
306
307 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
308
309 return failLabel;
310}
311
312template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
313StateType Result::result ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string, const StateType & failLabel ) {
314 ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > res = Run::calculateState ( automaton, string );
315
316 if ( std::get < 0 > ( res ) ) return std::get < 1 > ( res );
317
318 return failLabel;
319}
320
321} /* namespace run */
322
323} /* namespace automaton */
324
automaton::ArcFactoredDeterministicZAutomaton
Deterministic Z-Automaton in Arc-Factored Normal Form. Computation model for unranked regular tree la...
Definition: ArcFactoredDeterministicZAutomaton.h:65
automaton::DFA
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
automaton::DFTA
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
automaton::DPDA
Deterministic pushdown automaton. Accepts subset of context free languages.
Definition: DPDA.h:78
automaton::InputDrivenDPDA
Deterministic input driven pushdown automaton. Accepts subset of context free languages.
Definition: InputDrivenDPDA.h:79
automaton::RealTimeHeightDeterministicDPDA
Deterministic real time height deterministic pushdown automaton. Accepts subset of context free langu...
Definition: RealTimeHeightDeterministicDPDA.h:89
automaton::VisiblyPushdownDPDA
Deterministic visibly pushdown automaton. Accepts subset of context free languages.
Definition: VisiblyPushdownDPDA.h:86
automaton::run::Result
Implementation of automaton run over its input returning the reached state.
Definition: Result.h:30
automaton::run::Result::result
static StateType result(const automaton::DFA< SymbolType, StateType > &automaton, const string::LinearString< SymbolType > &string)
Definition: Result.h:224
ext::deque
Class extending the deque class from the standard library. Original reason is to allow printing of th...
Definition: deque.hpp:44
ext::tuple
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
string::LinearString
Linear string.
Definition: LinearString.h:57
tree::RankedTree
Tree structure represented in its natural representation. The representation is so called ranked,...
Definition: RankedTree.h:72
tree::UnrankedTree
Tree represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedTree.h:69
automaton::convert::StateType
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
automaton
Definition: ToGrammar.h:31
tree
Definition: BackwardOccurrenceTest.h:17
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2