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 <regexp/unbounded/UnboundedRegExp.h>
9
10#include <regexp/unbounded/UnboundedRegExpAlternation.h>
11#include <regexp/unbounded/UnboundedRegExpConcatenation.h>
12#include <regexp/unbounded/UnboundedRegExpElement.h>
13#include <regexp/unbounded/UnboundedRegExpEmpty.h>
14#include <regexp/unbounded/UnboundedRegExpEpsilon.h>
15#include <regexp/unbounded/UnboundedRegExpIteration.h>
16#include <regexp/unbounded/UnboundedRegExpSymbol.h>
17
18namespace regexp {
19
24class GlushkovIndexate {
25public:
30 template < class SymbolType >
31 static regexp::UnboundedRegExp < ext::pair < SymbolType, unsigned > > index ( const regexp::UnboundedRegExp < SymbolType > & re );
32
33 template < class SymbolType >
34 class Unbounded {
35 public:
36 static ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpAlternation < SymbolType > & alternation, unsigned & i);
37 static ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpConcatenation < SymbolType > & concatenation, unsigned & i);
38 static ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpIteration < SymbolType > & iteration, unsigned & i);
39 static ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpSymbol < SymbolType > & symbol, unsigned & i);
40 static ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpEpsilon < SymbolType > & epsilon, unsigned & i);
41 static ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpEmpty < SymbolType > & empty, unsigned & i);
42 };
43
48 template < class SymbolType >
49 static regexp::FormalRegExp < ext::pair < SymbolType, unsigned > > index ( const regexp::FormalRegExp < SymbolType > & re );
50
51 template < class SymbolType >
52 class Formal {
53 public:
54 static ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::FormalRegExpAlternation < SymbolType > & alternation, unsigned & i);
55 static ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::FormalRegExpConcatenation < SymbolType > & concatenation, unsigned & i);
56 static ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::FormalRegExpIteration < SymbolType > & iteration, unsigned & i);
57 static ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::FormalRegExpSymbol < SymbolType > & symbol, unsigned & i);
58 static ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::FormalRegExpEpsilon < SymbolType > & epsilon, unsigned & i);
59 static ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > visit(const regexp::FormalRegExpEmpty < SymbolType > & empty, unsigned & i);
60 };
61};
62
63template < class SymbolType >
64UnboundedRegExp < ext::pair < SymbolType, unsigned > > GlushkovIndexate::index ( const regexp::UnboundedRegExp < SymbolType > & re ) {
65 unsigned i = 1;
66
67 return UnboundedRegExp < ext::pair < SymbolType, unsigned > > ( regexp::UnboundedRegExpStructure < ext::pair < SymbolType, unsigned > > ( re.getRegExp ( ).getStructure ( ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Unbounded < SymbolType > > ( i ) ) );
68}
69
70template < class SymbolType >
71ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpAlternation < SymbolType > & alternation, unsigned & i) {
72 UnboundedRegExpAlternation < ext::pair < SymbolType, unsigned > > alt;
73
74 for ( const UnboundedRegExpElement < SymbolType > & element : alternation.getElements ( ) )
75 alt.appendElement ( element.template accept < ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Unbounded < SymbolType > > ( i ) );
76
77 return ext::ptr_value < UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > ( std::move ( alt ) );
78}
79
80template < class SymbolType >
81ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpConcatenation < SymbolType > & concatenation, unsigned & i) {
82 UnboundedRegExpConcatenation < ext::pair < SymbolType, unsigned > > con;
83
84 for ( const UnboundedRegExpElement < SymbolType > & element : concatenation.getElements ( ) )
85 con.appendElement ( element.template accept < ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Unbounded < SymbolType > > ( i ) );
86
87 return ext::ptr_value < UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > ( std::move ( con ) );
88}
89
90template < class SymbolType >
91ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpIteration < SymbolType > & iteration, unsigned & i) {
92 return ext::ptr_value < UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > ( UnboundedRegExpIteration < ext::pair < SymbolType, unsigned > > ( iteration.getElement ( ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < DefaultSymbolType, unsigned > > >, GlushkovIndexate::Unbounded < SymbolType > > ( i ) ) );
93}
94
95template < class SymbolType >
96ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpSymbol < SymbolType > & symbol, unsigned & i) {
97 return ext::ptr_value < UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > ( UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > ( ext::make_pair ( symbol.getSymbol ( ), i++ ) ) );
98}
99
100template < class SymbolType >
101ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpEpsilon < SymbolType > &, unsigned &) {
102 return ext::ptr_value < UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > ( UnboundedRegExpEpsilon < ext::pair < SymbolType, unsigned > > ( ) );
103}
104
105template < class SymbolType >
106ext::ptr_value < regexp::UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpEmpty < SymbolType > &, unsigned &) {
107 return ext::ptr_value < UnboundedRegExpElement < ext::pair < SymbolType, unsigned > > > ( UnboundedRegExpEmpty < ext::pair < SymbolType, unsigned > > ( ) );
108}
109
110template < class SymbolType >
111FormalRegExp < ext::pair < SymbolType, unsigned > > GlushkovIndexate::index ( const regexp::FormalRegExp < SymbolType > & re ) {
112 unsigned i = 1;
113
114 return FormalRegExp < ext::pair < SymbolType, unsigned > > ( regexp::FormalRegExpStructure < ext::pair < SymbolType, unsigned > > ( re.getRegExp ( ).getStructure ( ).template accept < ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i ) ) );
115}
116
117template < class SymbolType >
118ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit(const regexp::FormalRegExpAlternation < SymbolType > & alternation, unsigned & i) {
119 ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > left = alternation.getLeftElement ( ).template accept < ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
120 ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > right = alternation.getRightElement ( ).template accept < ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
121 return ext::ptr_value < FormalRegExpElement < ext::pair < SymbolType, unsigned > > > ( FormalRegExpAlternation < ext::pair < SymbolType, unsigned > > ( left, right ) );
122}
123
124template < class SymbolType >
125ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit(const regexp::FormalRegExpConcatenation < SymbolType > & concatenation, unsigned & i) {
126ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > left = concatenation.getLeftElement ( ).template accept < ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
127ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > right = concatenation.getRightElement ( ).template accept < ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i );
128 return ext::ptr_value < FormalRegExpElement < ext::pair < SymbolType, unsigned > > > ( FormalRegExpConcatenation < ext::pair < SymbolType, unsigned > > ( left, right ) );
129}
130
131template < class SymbolType >
132ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit(const regexp::FormalRegExpIteration < SymbolType > & iteration, unsigned & i) {
133 return ext::ptr_value < FormalRegExpElement < ext::pair < SymbolType, unsigned > > > ( FormalRegExpIteration < ext::pair < SymbolType, unsigned > > ( iteration.getElement ( ).template accept < ext::ptr_value < regexp::FormalRegExpElement < ext::pair < DefaultSymbolType, unsigned > > >, GlushkovIndexate::Formal < SymbolType > > ( i ) ) );
134}
135
136template < class SymbolType >
137ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit(const regexp::FormalRegExpSymbol < SymbolType > & symbol, unsigned & i) {
138 return ext::ptr_value < FormalRegExpElement < ext::pair < SymbolType, unsigned > > > ( FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > ( ext::make_pair ( symbol.getSymbol ( ), i++ ) ) );
139}
140
141template < class SymbolType >
142ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit(const regexp::FormalRegExpEpsilon < SymbolType > &, unsigned &) {
143 return ext::ptr_value < FormalRegExpElement < ext::pair < SymbolType, unsigned > > > ( FormalRegExpEpsilon < ext::pair < SymbolType, unsigned > > ( ) );
144}
145
146template < class SymbolType >
147ext::ptr_value < regexp::FormalRegExpElement < ext::pair < SymbolType, unsigned > > > GlushkovIndexate::Formal < SymbolType >::visit(const regexp::FormalRegExpEmpty < SymbolType > &, unsigned &) {
148 return ext::ptr_value < FormalRegExpElement < ext::pair < SymbolType, unsigned > > > ( FormalRegExpEmpty < ext::pair < SymbolType, unsigned > > ( ) );
149}
150
151} /* namespace regexp */
152
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
regexp::FormalRegExpAlternation
Represents the alternation operator in the regular expression. The node must have exactly two childre...
Definition: FormalRegExpAlternation.h:44
regexp::FormalRegExpConcatenation
Represents the concatenation operator in the regular expression. The node must have exactly two child...
Definition: FormalRegExpConcatenation.h:44
regexp::FormalRegExpEmpty
Represents the empty expression in the regular expression. The node can't have any children.
Definition: FormalRegExpEmpty.h:41
regexp::FormalRegExpEpsilon
Represents the epsilon expression in the regular expression. The node can't have any children.
Definition: FormalRegExpEpsilon.h:41
regexp::FormalRegExpIteration
Represents the iteration operator in the regular expression. The node has exactly one child.
Definition: FormalRegExpIteration.h:44
regexp::FormalRegExpStructure
Represents formal regular expression structure. Regular expression is stored as a tree of FormalRegEx...
Definition: FormalRegExpStructure.h:45
regexp::FormalRegExpSymbol
Represents the symbol in the regular expression. The can't have any children.
Definition: FormalRegExpSymbol.h:42
regexp::FormalRegExp
Formal regular expression represents regular expression. It describes regular languages....
Definition: FormalRegExp.h:78
regexp::FormalRegExp::getRegExp
const FormalRegExpStructure< SymbolType > & getRegExp() const &
Definition: FormalRegExp.h:208
regexp::GlushkovIndexate::Formal
Definition: GlushkovIndexate.h:52
regexp::GlushkovIndexate::Formal::visit
static ext::ptr_value< regexp::FormalRegExpElement< ext::pair< SymbolType, unsigned > > > visit(const regexp::FormalRegExpAlternation< SymbolType > &alternation, unsigned &i)
Definition: GlushkovIndexate.h:118
regexp::GlushkovIndexate::Unbounded
Definition: GlushkovIndexate.h:34
regexp::GlushkovIndexate::Unbounded::visit
static ext::ptr_value< regexp::UnboundedRegExpElement< ext::pair< SymbolType, unsigned > > > visit(const regexp::UnboundedRegExpAlternation< SymbolType > &alternation, unsigned &i)
Definition: GlushkovIndexate.h:71
regexp::GlushkovIndexate
Definition: GlushkovIndexate.h:24
regexp::GlushkovIndexate::index
static regexp::UnboundedRegExp< ext::pair< SymbolType, unsigned > > index(const regexp::UnboundedRegExp< SymbolType > &re)
regexp::GlushkovIndexate::index
static regexp::FormalRegExp< ext::pair< SymbolType, unsigned > > index(const regexp::FormalRegExp< SymbolType > &re)
regexp::UnboundedRegExpAlternation
Represents the alternation operator in the regular expression. The node can have 0 to n children in l...
Definition: UnboundedRegExpAlternation.h:44
regexp::UnboundedRegExpAlternation::appendElement
void appendElement(UnboundedRegExpElement< SymbolType > &&element)
Definition: UnboundedRegExpAlternation.h:195
regexp::UnboundedRegExpConcatenation
Represents the concatenation operator in the regular expression. The node can have 0 to n children in...
Definition: UnboundedRegExpConcatenation.h:44
regexp::UnboundedRegExpConcatenation::appendElement
void appendElement(UnboundedRegExpElement< SymbolType > &&element)
Definition: UnboundedRegExpConcatenation.h:195
regexp::UnboundedRegExpElement
Definition: UnboundedRegExpElement.h:62
regexp::UnboundedRegExpEmpty
Represents the empty expression in the regular expression. The node can't have any children.
Definition: UnboundedRegExpEmpty.h:41
regexp::UnboundedRegExpEpsilon
Represents the epsilon expression in the regular expression. The node can't have any children.
Definition: UnboundedRegExpEpsilon.h:41
regexp::UnboundedRegExpIteration
Represents the iteration operator in the regular expression. The node has exactly one child.
Definition: UnboundedRegExpIteration.h:43
regexp::UnboundedRegExpStructure
Represents unbounded regular expression structure. Regular expression is stored as a tree of Unbounde...
Definition: UnboundedRegExpStructure.h:47
regexp::UnboundedRegExpSymbol
Represents the symbol in the regular expression. The can't have any children.
Definition: UnboundedRegExpSymbol.h:42
regexp::UnboundedRegExp
Unbounded regular expression represents regular expression. It describes regular languages....
Definition: UnboundedRegExp.h:80
regexp::UnboundedRegExp::getRegExp
const UnboundedRegExpStructure< SymbolType > & getRegExp() const &
Definition: UnboundedRegExp.h:210
automaton::properties::i
int i
Definition: AllEpsilonClosure.h:118
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
regexp
Definition: ToAutomaton.h:15
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2