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
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