Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
GlushkovIndexate.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <common/ranked_symbol.hpp>
9#include <alib/pair>
10
11#include <rte/formal/FormalRTE.h>
12#include <rte/formal/FormalRTEElements.h>
13
14namespace rte {
15
16class GlushkovIndexate {
17public:
22 template < class SymbolType >
23 static FormalRTE < ext::pair < SymbolType, unsigned > > index ( const rte::FormalRTE < SymbolType > & rte ) {
24 unsigned i = 1;
25
26 return FormalRTE < ext::pair < SymbolType, unsigned > > ( FormalRTEStructure < ext::pair < SymbolType, unsigned > > ( rte.getRTE ( ).getStructure ( ).template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i ) ) );
27 }
28
29 template < class SymbolType >
30 class Formal {
31 public:
32 static ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > visit ( const rte::FormalRTEAlternation < SymbolType > & node, unsigned & i );
33 static ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > visit ( const rte::FormalRTESubstitution < SymbolType > & node, unsigned & i );
34 static ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > visit ( const rte::FormalRTEIteration < SymbolType > & node, unsigned & i );
35 static ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > visit ( const rte::FormalRTESymbolAlphabet < SymbolType > & node, unsigned & i );
36 static ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > visit ( const rte::FormalRTESymbolSubst < SymbolType > & node, unsigned & i );
37 static ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > visit ( const rte::FormalRTEEmpty < SymbolType > & node, unsigned & i );
38 };
39
40};
41
42template < class SymbolType >
43ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit ( const rte::FormalRTESymbolAlphabet < SymbolType > & node, unsigned & i ) {
44 ext::pair < SymbolType, unsigned > sps = ext::make_pair ( node.getSymbol ( ).getSymbol ( ), i ++ );
45 ext::ptr_vector < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > > children;
46 for ( const rte::FormalRTEElement < SymbolType > & e : node.getElements ( ) ) {
47 children.push_back ( static_cast < FormalRTEElement < ext::pair < SymbolType, unsigned > > && > ( e.template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i ) ) );
48 }
49
50 return ext::ptr_value < FormalRTESymbolAlphabet < ext::pair < SymbolType, unsigned > > > ( FormalRTESymbolAlphabet < ext::pair < SymbolType, unsigned > > ( common::ranked_symbol < ext::pair < SymbolType, unsigned > > ( sps , node.getSymbol ( ).getRank ( ) ), std::move ( children ) ) );
51}
52
53template < class SymbolType >
54ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit ( const rte::FormalRTESymbolSubst < SymbolType > & node, unsigned & ) {
55 return ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > ( FormalRTESymbolSubst < ext::pair < SymbolType, unsigned > > ( common::ranked_symbol < ext::pair < SymbolType, unsigned > > ( ext::make_pair ( node.getSymbol ( ).getSymbol ( ), 0u ), node.getSymbol ( ).getRank ( ) ) ) );
56}
57
58template < class SymbolType >
59ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit ( const rte::FormalRTEAlternation < SymbolType > & node, unsigned & i ) {
60 ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > > left = node.getLeftElement ( ).template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
61 ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > > right = node.getRightElement ( ).template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
62 return ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > ( FormalRTEAlternation < ext::pair < SymbolType, unsigned > > ( std::move ( left ), std::move ( right ) ) );
63}
64
65template < class SymbolType >
66ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit ( const rte::FormalRTESubstitution < SymbolType > & node, unsigned & i ) {
67 ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > > left = node.getLeftElement ( ).template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
68 ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > > right = node.getRightElement ( ).template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
69 FormalRTESymbolSubst < ext::pair < SymbolType, unsigned > > substSymbol ( common::ranked_symbol < ext::pair < SymbolType, unsigned > > ( ext::make_pair ( node.getSubstitutionSymbol ( ).getSymbol ( ).getSymbol ( ), 0u ), node.getSubstitutionSymbol ( ).getSymbol ( ).getRank ( ) ) );
70 return ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > ( FormalRTESubstitution < ext::pair < SymbolType, unsigned > > ( std::move ( left ), std::move ( right ), std::move ( substSymbol ) ) );
71}
72
73template < class SymbolType >
74ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit ( const rte::FormalRTEIteration < SymbolType > & node, unsigned & i ) {
75 ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > > element = node.getElement ( ).template accept < ext::ptr_value < rte::FormalRTEElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
76 FormalRTESymbolSubst < ext::pair < SymbolType, unsigned > > substSymbol ( common::ranked_symbol < ext::pair < SymbolType, unsigned > > ( ext::make_pair ( node.getSubstitutionSymbol ( ).getSymbol ( ).getSymbol ( ), 0u ), node.getSubstitutionSymbol ( ).getSymbol ( ).getRank ( ) ) );
77 return ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > ( FormalRTEIteration < ext::pair < SymbolType, unsigned > > ( std::move ( element ), std::move ( substSymbol ) ) );
78}
79
80template < class SymbolType >
81ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit ( const rte::FormalRTEEmpty < SymbolType > &, unsigned & ) {
82 return ext::ptr_value < FormalRTEElement < ext::pair < SymbolType, unsigned > > > ( FormalRTEEmpty < ext::pair < SymbolType, unsigned > > ( ) );
83}
84
85} /* namespace rte */
86
common::ranked_symbol
Definition: ranked_symbol.hpp:20
ext::pair
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
ext::ptr_value
Class representing wrapper of dynamically allocated object behaving like rvalue reference.
Definition: ptr_value.hpp:40
ext::ptr_vector
Implementation of vector storing dynamicaly allocated instances of given type. The class mimicks the ...
Definition: ptr_vector.hpp:44
ext::ptr_vector::push_back
void push_back(R &&value)
Appends a new value at the end of the container.
Definition: ptr_vector.hpp:1228
rte::FormalRTEAlternation
Represents the alternation operator in the regular tree expression. The node must have exactly two ch...
Definition: FormalRTEAlternation.h:44
rte::FormalRTEElement
Definition: FormalRTEElement.h:54
rte::FormalRTEEmpty
Represents the empty expression in the regular tree expression. The node can't have any children.
Definition: FormalRTEEmpty.h:40
rte::FormalRTEIteration
Represents the iteration operator in the regular tree expression. The node has exactly one child.
Definition: FormalRTEIteration.h:45
rte::FormalRTEStructure
Represents unbounded regular expression structure. Regular expression is stored as a tree of Unbounde...
Definition: FormalRTEStructure.h:41
rte::FormalRTESubstitution
Represents the concatenation operator in the regular tree expression. The node must have exactly two ...
Definition: FormalRTESubstitution.h:44
rte::FormalRTESymbolAlphabet
Represents the terminal symbol in the regular tree expression. The number of children must be the sam...
Definition: FormalRTESymbolAlphabet.h:44
rte::FormalRTESymbolSubst
Represents the substitution symbol in the regular tree expression. The node can't have any children.
Definition: FormalRTESymbolSubst.h:43
rte::FormalRTE
Formal regular tree expression represents regular tree expression. It describes regular tree language...
Definition: FormalRTE.h:71
rte::GlushkovIndexate::Formal
Definition: GlushkovIndexate.h:30
rte::GlushkovIndexate::Formal::visit
static ext::ptr_value< FormalRTEElement< ext::pair< SymbolType, unsigned > > > visit(const rte::FormalRTEAlternation< SymbolType > &node, unsigned &i)
Definition: GlushkovIndexate.h:59
rte::GlushkovIndexate
Definition: GlushkovIndexate.h:16
rte::GlushkovIndexate::index
static FormalRTE< ext::pair< SymbolType, unsigned > > index(const rte::FormalRTE< SymbolType > &rte)
Definition: GlushkovIndexate.h:23
automaton::properties::i
int i
Definition: AllEpsilonClosure.h:118
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
node
Definition: Node.cpp:11
rte
Definition: ToFTAGlushkov.h:22
ranked_symbol.hpp
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2